問題文
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小笼包