Good Pizza 是一家著名的披萨店。由于外卖订单数量不断增加，店里比以往更加忙碌。

有一天，店里同时收到了多份订单！共有 $N$ 份订单，由 $N$ 位顾客下单。第 $i$ 位顾客下了第 $i$ 份订单。

通过以往的订单，店里掌握了每位顾客的信息。对于第 $i$ 位顾客，从店里送披萨过去需要 $t_i$ 小时，从顾客处返回店里也需要 $t_i$ 小时。此外，该顾客的“易怒值”为 $a_i$。一个人的易怒值越高，就越容易生气。

Good Pizza 必须为顾客配送订单，并尽量减少顾客的压力。为了量化第 $i$ 位顾客感受到的压力，设 $h_i$ 为从下单到送达的时间，设 $p_i$ 为送达时间比第 $i$ 位顾客更快的其他顾客人数。第 $i$ 位顾客的压力值 ($s_i$) 计算公式如下：

$$s_i = a_i \times (h_i + p_i)$$

为了减轻顾客压力并获得高满意度，需要制定更好的配送计划。在考虑这个问题时，必须考虑以下几点：

• 只有一名配送员。
• 配送员不能同时配送多份订单。这意味着他/她一次只能配送一份订单，送达后，他/她必须返回店里才能配送下一份订单。
• 可以假设准备订单、从店里交给配送员以及从配送员交给顾客的过程不耗费时间。

你是 Good Pizza 的配送规划师。根据上述信息和条件，你需要最小化所有顾客的总压力值。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 100\,000$)，表示顾客人数。

接下来的 $N$ 行中，第 $i$ 行包含两个整数 $t_i$ 和 $a_i$，分别表示从店里到第 $i$ 位顾客的配送时间（往返各需 $t_i$ 小时，$1 \le t_i \le 1\,000$）以及该顾客的易怒值 $a_i$ ($1 \le a_i \le 1\,000$)。

输出格式

输出最小的总压力值。

样例

样例输入 1

3
10 3
3 8
4 2

样例输出 1

124

样例输入 2

10
17 62
30 79
99 2
88 57
42 46
84 11
44 60
21 98
68 63
17 54

样例输出 2

118250