本题没有可用的提交语言。

描述

从前，在一个小岛上有一个小王国。国王需要奖赏一位将军，以表彰他抗击敌人的功绩。这位国王以吝啬著称。因此，国王给了将军一张$10000 \times 10000$的绿色矩形地图。（我们称矩形的宽度为较短的一边，另一边称为高度。因此，一个$3 \times 4$的矩形宽度为$3$，高度为$4$。）将军最多可以从桌上选择$100$组蓝色矩形。每组包含至少$2$个、最多$15$个矩形，且同一组中矩形的宽度相同。我们还知道，如果矩形$A$和矩形$B$属于不同的组，那么$A$不包含$B$，且$B$不包含$A$。（注意，矩形有$4$条边界线。平面中的两条线如果被同一条直线包含，则称为对齐。矩形$A$包含矩形$B$，当且仅当可以将$A$完全放置在$B$的顶部，使得$A$的至少一条边界线与$B$的一条边界线对齐，并且假设矩形是实心且不透明的，$B$的任何部分都不可见。例如，一个$5 \times 7$的矩形包含一个$4 \times 6$的矩形，但一个$5 \times 5$的矩形不包含一个$4 \times 6$的矩形。）蓝色矩形的总数不超过$1000$个。

将军可以从桌上选择任意数量的蓝色矩形，并将它们放置在绿色矩形的顶部。每个蓝色矩形必须有一个角落位于绿色矩形的左下角，并且蓝色矩形的一条边界线与绿色矩形的一条边界线对齐。

被蓝色矩形覆盖的地图区域将授予将军。这对将军来说似乎是一项艰巨的任务。幸运的是，将军有一台笔记本电脑。请帮助将军编写一个程序，找出这些蓝色矩形能覆盖的最大面积。你不需要展示如何放置蓝色矩形。输出是将军能获得的最大面积。例如，如果有两个蓝色矩形，尺寸分别为$5 \times 7$和$5 \times 6$，它们属于同一组。下图展示了两种可能的放置方式。

在左侧，覆盖的总面积为$35$。在右侧，覆盖的总面积为$40$，这是你能覆盖的最大面积。

输入

输入包含$m$组测试数据，$m \leq 10$。每组测试数据中最多有$1000$个矩形。第一行为矩形数量。每组数据中的每个矩形用一行$x\ y$表示，其中$x$和$y$分别是矩形的宽度和高度。$x$和$y$之间有一个空格。注意，$x$和$y$是不超过$10000$的正整数。输入文件的结尾是一行单独的$-1$。

输出

输出应包含$m$行，每行一个数字，表示对应数据集的最大覆盖面积。

输入数据 1

2
5 7
5 6
-1

输出数据 1

40

来源

台湾 2004