C - ガソリンスタンド Editorial /

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

石油王となったすぬけ君はガソリンをこよなく愛していて、王国内の移動には車を欠かさず使う。
王国にはN個のガソリンスタンドがあり、i 個目のガソリンスタンドではガソリンが 1 Lあたり V_i 円で売っている。

また、ガソリンスタンドは 1 番目から N 番目まで一直線上に並んでおり、i 個目とj 個目のガソリンスタンドを移動するのには|i-j| Lのガソリンが必要である。

さて、すぬけ君は 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

遠回りをしていく方がよい場合もあることに注意せよ。