Let us observe a stable arrangement of rectangles. The stability condition requires that the X-barycentre of all rectangles other than the lowest one has distance of at most ~1~ unit from the X-centre of the lowest rectangle. If we also factor in the mass of the lowest rectangle, we obtain the X-barycentre of the whole arrangement which also has distance of at most ~1~ unit from the X-centre of the lowest rectangle.

Let ~dx(S)~ be the difference of the x-coordinate of the rightmost point of some rectangle in the arrangement ~S~ and the X-barycentre of the arrangement. This value stays constant if the arrangement is translated along the X-axis.

Let us denote a stable arrangement of the top ~k~ rectangles with ~S_k~. We will deem ~S_k~ as optimal if there exists no arrangement of the top ~k~ rectangles with a larger ~dx~ value than ~S_k~.

The required solution of the problem is ~dx(S_{n-1})+1~, for some optimal ~S_{n-1}~.

The optimal arrangements can be determined using dynamic programming. For each state, we memorize ~dx~ and the total mass ~M~ of the current optimal arrangement.

The trivial case is ~S_1~, with values ~dx = 1~, ~M =~ mass of the last rectangle in input.

Determining ~S_{j+1}~ from ~S_j~:

The rectangle ~j+1~ (counting from the top) is placed under the current arrangement, with two possible cases:

• the X-barycentre of ~S_j~ coincides with the upper right corner of the new rectangle
• the X-barycentre of ~S_j~ coincides with the upper left corner of the new rectangle

We simply select the new arrangement with the larger ~dx~ value among the two possibilities.