你用了俄羅斯娃娃許了願，而這些俄羅斯娃娃也為了救出最底層的娃娃而實現了願望。然而為了救出娃娃，有些娃娃的法力變為負的了。

厭煩了上一種許願方法的你，決定再試試另一個坊間流傳的許願方法。為此，你隨機地將這些俄羅斯娃娃排成了 $n \times n$ 的方陣（$n\leq 500$）並搬來一個超級無敵大的俄羅斯娃娃。這個俄羅斯娃娃雖然足夠大，但每次只能裝入某個矩形內的所有俄羅斯娃娃（也可以不放任何娃娃）。而為了讓願望比較容易成真，你當然希望大俄羅斯娃娃所裝的俄羅斯娃娃法力總和最大。

要注意，這種許願方法是不允許移動已隨機放好的俄羅斯娃娃們。如果你移動了，法力會和你產生排斥，讓你變成俄羅斯娃娃。而你只有一次將俄羅斯娃娃裝入大俄羅斯娃娃的機會，所以你希望藉由程式幫助你找出最好的許願方法。