AT_tkppc3_f 天使とふすま

[problemUrl]: https://atcoder.jp/contests/tkppc3/tasks/tkppc3_f 配点： $ 700 $ 点 T さんは天界から降りてきて, 下界の勉強をしている天使である. 今日はとある館で手伝いをしながら和室の勉強をしており, 館の主人にふすまを閉めるように言われた. 美しいこの館にはふすま $ 1 $ からふすま $ N $ までの $ N $ 枚のふすまがあるが, ふすまの一つ一つが芸術作品なので, それぞれ幅と重さが違う. 中にはとても重いものもあり, T さんは体力が尽きないか心配になった. 今, $ N $ 枚のふすまは, 部屋の片方の端に揃っている. ふすま $ i $ は幅が $ A_i $ であり, 重さが $ B_i $である. 全てのふすまの幅を合計すると, 部屋と部屋の境目の幅 (ふすまを動かせる幅) と同じになる. また, 彼女は重さ $ x $ のふすまを長さ $ y $ 移動させると, 体力を $ xy $ 消費する. 心配性な T さんのために, ふすまを完全に閉め切るのに必要な体力の合計の最小値を求めよ.

入力は, 以下の形式で標準入力から与えられる. > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ A_3 $ $ B_3 $ ... $ A_N $ $ B_N $

T さんがふすまを完全に閉め切るのに必要な体力の最小値を出力しなさい.

### 制約 - $ N $ は $ 1 $ 以上 $ 200\ 000 $ 以下の整数である. - $ A_i $, $ B_i $ ($ 1\ \leq\ i\ \leq\ N $) は $ 1 $ 以上 $ 10\ 000 $ 以下の整数である. ### 小課題 小課題1 \[ $ 200 $点 \] - $ N\ \leq\ 10 $ を満たす. 小課題2 \[ $ 500 $点 \] - 追加の制約はない. ### Sample Explanation 1 !\[\](https://img.atcoder.jp/tkppc3/f9bd9962311937984dec1b84277acccc.png)上の図のように, ふすまを (ふすま $ 3 $) -> (ふすま $ 2 $) -> (ふすま $ 1 $) の順番で並べたら, 必要な体力は $ 0\ *\ 4\ +\ 3\ *\ 3\ +\ (3\ +\ 5)\ *\ 1\ =\ 17 $ となる. ### Sample Explanation 2 ふすまを (ふすま $ 3 $) -> (ふすま $ 5 $) -> (ふすま $ 1 $) -> (ふすま $ 2 $) -> (ふすま $ 4 $) の順に並べたら, 必要な体力は $ 0\ *\ 4\ +\ 2\ *\ 1\ +\ 3\ *\ 4\ +\ 8\ *\ 3\ +\ 12\ *\ 2\ =\ 62 $ となる.