该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

假设这是一个二次元。
LYK召集了n个小伙伴一起来拍照。他们分别有自己的身高Hi和宽度Wi。
为了放下这个照片并且每个小伙伴都完整的露出来，必须需要一个宽度为ΣWi，高度为max{Hi}的相框。（因为不能叠罗汉）。
LYK为了节省相框的空间，它有了绝妙的idea，让部分人躺着！一个人躺着相当于是身高变成了Wi，宽度变成了Hi。但是很多人躺着不好看，于是规定最多只有n/2个人躺着。（也就是说当n=3时最多只有1个人躺着，当n=4时最多只有2个人躺着）
现在想问你，当其中部分人躺着后，相框的面积最少是多少。

Fomat

Input

第一行一个数n。
接下来n行，每行两个数分别是Wi,Hi。

Output

你需要输出这个相框的面积最少是多少。

Sample 1

Input

3 
3 1 
2 2 
4 3 

Output

21

Hint

【输入提示】
如果没人躺过来，需要27的面积。
我们只要让第1个人躺过来，就只需要21的面积！
【数据范围】
对于100%的数据\(1<=n,Wi,Hi<=1000\)。