← 返回题目列表

AtCoder · tkppc3_f

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点 ]

  • 没有其他限制。

入力例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 变为。

作者: ynym小笼包