题目描述

七萤拥有$\mathit n$ 件物品，每件物品有两种属性 $a,b$，七萤需要依次决定每件物品的属性归属（每件物品最终有且只能有一种属性）。七萤的初始战斗力值为$0$。

属性加成条件： 设当前决定第$i$件物品的属性归属，且之前已经选择了 $n_a$ 件 $a$ 属性物品， $n_b$ 件 $b$ 属性物品，则当前物品若选择 $a$ 属性，七萤会获得$(n_a + 1) \times a_i$ 的战斗力，若选择 $b$ 属性，七萤会获得$(n_b+1) \times b_i$的战斗力。

属性平衡条件： 若七萤最终拥有$f_a$ 件 $a$ 属性物品和 $f_b$ 件 $b$ 属性物品（显然$f_a+f_b=n$），七萤会减少 $(f_a-f_b)^2$ 的战斗力。

物品品质条件： 在这 $n$ 件物品中，没有两件物品的两个属性值互相大于对方（即对于任意物品 $i,j$ ($1\le i,j\le n$)，不存在 $a_i>a_j$ 且 $b_j>b_i$）。

七萤可以自行决定这 $n$ 件物品的选择顺序。在满足上述条件下，七萤能获得的最大战斗力值是多少？

输入格式

第一行一个正整数 $n$，含义如上所述。

接下来 $n$ 行，每行两个整数，第 $i$ 行表示第 $i$ 件物品的两个属性值 $a_i,b_i$ 。

输出格式

一个整数，表示答案。

3
1 1
3 2
4 6

15

样例解释

首选选择第一件物品的 $b$ 属性，获得加成值$1 \times 1 = 1$，然后选择第二件物品的 $a$ 属性，获得加成值$1 \times 3 = 3$，最后选择第三件物品的 $b$ 属性，获得加成$2 \times 6=12$，当前总战斗力为$1+3+12=16$，最后总共选择了$1$件 $a$ 属性物品和$2$件 $b$ 属性物品，减少$(1-2)^2=1$点战斗力，最终战斗力为$15$。

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 2 \times 10^{3},0 \leq a_i,b_i \leq 10^6$。