题目描述

FJ 准备扩大他的农场，他正在考虑 $n$ 块长方形的土地。每块土地的长为 $l$，宽为 $w$。每块土地的价格是它的面积，但 FJ 可以同时购买多块土地。这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换。如果FJ买一块 $3\times5$ 的地和一块 $5\times3$ 的地，则他需要付 $5\times5=25$。FJ希望买下所有的土地，但是他发现分组来买这些土地可以节省经费。他需要你帮助他找到最小的经费。

输入格式

第 $1$ 行：一个数：$n$

第 $2$ 至 $n+1$ 行：第 $i+1$ 行包含两个数,分别为第 $i$ 块土地的长和宽

输出格式

一个整数，代表最小的可行费用.

4
100 1
15 15
20 5
1 100

500

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 50000$，$1 \leq l , w \leq 1\times10^6$。

提示

样例中FJ分 $3$ 组买这些土地: 第一组: $100\times1$ , 第二组 $1\times100$ , 第三组 $20\times5$ 和 $15\times15$

价格分别为 $100$，$100$，$300$，总共 $500$。

来源

USACO 2008 May Gold