P2900 [USACO08MAR] Land Acquisition G

Farmer John is planning to expand his farm and is considering buying $N$ rectangular plots. If FJ buys a single plot, the price equals the area of the plot. But he can choose to acquire a group of plots together, where the price of the group is the maximum length times the maximum width among those plots. For example, if FJ acquires a $3 \times 5$ plot and a $5 \times 3$ plot together, he only pays $5 \times 5=25$, which is cheaper than buying them separately. FJ wants to buy all the plots. He found that partitioning the plots into different groups can save money. Given the dimensions of each plot, please help him compute the minimum total cost to purchase all plots.

The first line contains an integer $N$ ($1 \leq N \leq 5 \times 10^4$). Each of the next $N$ lines contains two integers $w_i$ and $l_i$, denoting the length and the width of the $i$-th plot. It is guaranteed that both the length and the width do not exceed $10^6$.

Output the minimum cost to buy all the plots.

Divide all plots into three groups: - The first plot is in the first group, costing $100 \times 1=100$. - The second and third plots are in the second group, costing $20 \times 15=300$. - The fourth plot is in the third group, costing $1 \times 100=100$. The total cost is $500$, and it can be proven that no better plan exists. Translated by ChatGPT 5