Mindful Rectangles Placement

You have organized n thoughts, each represented by a rectangle \(r_i\) with given width and height. You want to arrange these \(r_i\)'s inside a larger rectangle \(R\) so that:

• Every \(r_i\) is completely within \(R\),
• The sides of each \(r_i\) are parallel to the corresponding sides of \(R\), and
• Any two placed rectangles do not overlap (i.e. the overlapping area between any two is zero).

There are two placement modes:

1. Minimize \(R\)'s area: Place all n rectangles inside \(R\) and try to minimize the area of \(R\);
2. Maximize placement count: \(R\) is given with fixed dimensions, and you wish to place as many of the \(n\) rectangles as possible.

One feasible (but not necessarily optimal) strategy for mode 1 is to place all rectangles in a single row. In this arrangement, the width of \(R\) is the sum of all rectangle widths and its height is the maximum height among them. Hence, an achievable area is:

\[ A = \left(\sum_{i=1}^{n} w_i\right) \times \max_{1\le i \le n}\{h_i\}. \]

For mode 2, a greedy row‐packing strategy is adopted. After sorting the rectangles in ascending order by their heights (breaking ties by width), you pack them row by row. In each row, you add rectangles from left to right as long as the current rectangle fits in the remaining horizontal space of \(R\). When a rectangle does not fit in the current row, you start a new row (if the total vertical height remains within \(R\)). Rectangles that are too wide (i.e. \(w_i > R_{width}\)) cannot be placed. The goal is to count how many rectangles can be packed by this greedy strategy.

inputFormat

The first integer in the input indicates the placement mode:

• If it is 1, the problem is to place all rectangles with minimal area \(R\).
• If it is 2, the dimensions of \(R\) are fixed, and the goal is to place as many rectangles as possible.

Input formats:

If the first integer is 1:

1
n
w1 h1
w2 h2
...
wn hn

If the first integer is 2:

2
W H
n
w1 h1
w2 h2
...
wn hn

Here, n is the number of rectangles. For each rectangle \(r_i\), \(w_i\) and \(h_i\) denote its width and height, respectively. For mode 2, \(W\) and \(H\) (\(R_{width}\) and \(R_{height}\)) are the fixed dimensions of \(R\). All numbers are positive integers.

outputFormat

For mode 1, output a single integer representing the achieved area of \(R\) computed by placing all rectangles in one row, i.e.:

\[ A = \Bigl(\sum_{i=1}^{n} w_i\Bigr) \times \max_{1\le i \le n}\{h_i\}. \]

For mode 2, output a single integer representing the maximum number of rectangles that the greedy row‐packing algorithm can place into \(R\). If a rectangle cannot be placed because its width exceeds \(W\) or starting a new row would exceed the height \(H\), it is skipped.

sample

1
3
1 2
3 1
2 2

12

</p>