← 返回题目列表

AtCoder · ijpc2015_f

C. 加油站

中文机器翻译题面 查看原题

問題文

成为石油王的斯努克君非常喜欢加油站,在王国内移动时总是离不开汽车。
王国中有N个加油站,i 第 个加油站的汽油 1 每升 V_i 日元出售。

此外,加油站从第 1 个到第 N 个沿一条直线排列,i 从第 个到第j 个加油站移动需要|i-j| 升汽油。

现在,须乃子君计划进行为期 Q 天的加油站巡游。

i 第 天,他打算前往第 S_i 个到第 T_i 个加油站。为此,他可能会经过几个加油站;但是,每当在加油站停车时,即使那里就是目的地,也会付钱给汽车加满汽油。此外,必须在目的地停车,但不一定要在途中路线上的加油站停车,停车的加油站可以由司机自由选择。

须乃子君的司机须目可先生无法阻止须乃子君加油,因此决定调查停在哪些加油站,才能以最低费用在目的地加油站之间移动。

现在,轮到你出场了。请对于每条路线,求出须目可先生所需支付金额的最小值。

但是,保证每天旅程开始前汽车都已加满汽油,并且无论在任何加油站之间移动,须乃子君的汽车都不会耗尽汽油。


入力

输入是按以下格式从标准输入给出的。

 N   Q
V_1 V_2 ... V_N
S_1 T_1
S_2 T_2
...
S_Q T_Q
  • 第一行给出加油站的个数 N(1≦N≦4000) 以及须乃子君旅行的天数 Q(1≦Q≦200,000) 。
  • 下一行给出整数 N 个。i 作为第个整数, i 在第个加油站的 1 每 L 汽油的价格 V_{i}(1≦V_{i}≦100,000) 。
  • 继续 Q 在行中的 i 第行中 i(1≦i≦Q) 第天小助开始行驶的加油站 S_{i}(1≦S_{i}≦N) 以及作为终点的加油站 T_{i}(1≦T_{i}≦N) 以空格分隔给出。在此情况下,S_{i}≠T_{i} 保证为。

配点

本题没有部分分。

出力

i(1≦i≦Q) 线 i 请输出第天移动所需费用的最小值。


入力例1

3 3
5 3 4
3 1
1 2
2 1

出力例1

8
3
5

入力例2

5 5
9 5 10 6 6
5 1
2 1
2 3
1 4
1 4

出力例2

24
9
10
17
17

入力例3

6 1
100 100 100 5 3 1
1 4

出力例3

13

请注意,有时绕远路会更好。