問題文
成为石油王的斯努克君非常喜欢加油站,在王国内移动时总是离不开汽车。
王国中有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
请注意,有时绕远路会更好。