题目描述

七萤拥有 $\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_i>b_j$）。

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

输入格式

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

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

输出格式

一个整数，表示答案。

3
1 6
3 2
4 1

17

样例解释

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

数据规模与约定

下发文件

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

有合理的子任务依赖。

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