题目描述

给定 $n$ 个矩形块（矩形包括长方形和正方形），将这 $n$ 个矩形块从左往右一字排开（如下图）。 找出一个最小的封闭矩形将这 $n$ 个矩形块放入，但不得相互重叠。所谓最小矩形指该矩形面积最小。

输入格式

第一行一个整数 $n(n<20)$，接下来有 $n$ 行。每一行用两个正整数来表示一个给定的矩形块的两个边长。矩形块的每条边的边长范围 最小是 $1$，最大是 $110$。

输出格式

一行，$1$ 个整数，代表封闭矩形的最小面积。

样例

4
1 2
2 3
3 4
4 5

44

解释#1

这 样 放 置 4 个 矩 形 得 到 的 红 色 矩 形 是 最 小 的 ：

红色矩形块面积为 4 * 11=44。