luogu#P2900. [USACO08MAR] Land Acquisition G

[USACO08MAR] Land Acquisition G

题目描述

Farmer John 准备扩大他的农场,眼前他正在考虑购买 NN 块长方形的土地。

如果 FJ 单买一块土地,价格就是土地的面积。但他可以选择并购一组土地,并购的价格为这些土地中最大的长乘以最大的宽。比如 FJ 并购一块 3×53 \times 5 和一块 5×35 \times 3 的土地,他只需要支付 5×5=255 \times 5=25 元, 比单买合算。

FJ 希望买下所有的土地。他发现,将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸,请你帮助他计算购买所有土地所需的最小费用。

输入格式

第一行一个整数 NN1N5×1041 \leq N \leq 5 \times 10^4)。

接下来 NN 行,每行两个整数 wiw_ilil_i,代表第 ii 块土地的长和宽。保证土地的长和宽不超过 10610^6

输出格式

输出买下所有土地的最小费用。

4 
100 1 
15 15 
20 5 
1 100 

500 

提示

将所有土地分为三组:

  • 第一块土地为第一组,花费 100×1=100100 \times 1=100
  • 第二,三块土地为第二组,花费 20×15=30020 \times 15=300
  • 第四块土地为第三组,花费 1×100=1001 \times 100=100

总花费为 500500,可以证明不存在更优的方案。