問題文

T さんは天界から降りてきて, 下界の勉強をしている天使である. 今日はとある館で手伝いをしながら和室の勉強をしており, 館の主人にふすまを閉めるように言われた.

美しいこの館にはふすま $1$ からふすま $N$ までの $N$ 枚のふすまがあるが, ふすまの一つ一つが芸術作品なので, それぞれ幅と重さが違う. 中にはとても重いものもあり, T さんは体力が尽きないか心配になった.

今, $N$ 枚のふすまは, 部屋の片方の端に揃っている. ふすま $i$ は幅が $A_i$ であり, 重さが $B_i$である. 全てのふすまの幅を合計すると, 部屋と部屋の境目の幅 (ふすまを動かせる幅) と同じになる. また, 彼女は重さ $x$ のふすまを長さ $y$ 移動させると, 体力を $xy$ 消費する.

心配性な T さんのために, ふすまを完全に閉め切るのに必要な体力の合計の最小値を求めよ.

入力例1Copy

3
2 1
5 3
3 4

出力例1Copy

17

上の図のように, ふすまを (ふすま $3$) -> (ふすま $2$) -> (ふすま $1$) の順番で並べたら, 必要な体力は $0 * 4 + 3 * 3 + (3 + 5) * 1 = 17$ となる.

入力例2Copy

5
5 4
4 3
2 4
4 2
1 1

出力例2Copy

62

ふすまを (ふすま $3$) -> (ふすま $5$) -> (ふすま $1$) -> (ふすま $2$) -> (ふすま $4$) の順に並べたら, 必要な体力は $0 * 4 + 2 * 1 + 3 * 4 + 8 * 3 + 12 * 2 = 62$ となる.