問題文

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

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

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

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

入力例1

3
2 1
5 3
3 4

出力例1

17

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

入力例2

5
5 4
4 3
2 4
4 2
1 1

出力例2

62

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