森森快递

题目描述

森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的 N 个城市，这些城市从左到右依次从 0 到(N-1 )编号。由于道路限制，第 i 号城市（i=0, … , N-2） 与第( i+1 )号城市中间往返的运输货物重量在同一时刻不能超过 Cⁱ 公斤。

公司开张后很快接到了 Q 张订单，其中 j 张订单描述了某些指定的货物要从 S^j 号城市运输到 T^j号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。

为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？ 要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排 1 号城市到 4 号城市以及 2 号城市到 4 号城市两张订单的运输，则这两张订单的运输同时受 2-3 以及 3-4 两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。

时间限制： 5000        内存限制： 262144

输入

输入在第一行给出两个正整数 N 和 Q（2 ≤ N ≤ 1 0 5 , 1 ≤ Q ≤ 1 0 5 ） ，表示总共的城市数

以及订单数量。第二行给出(N-1 )个数，顺次表示相邻两城市间的道路允许的最大运货重量 C i （i=0, … , N-2） 。题目保证每个 Cⁱ是不超过 2³¹ 的非负整数。接下来 Q 行，每行给出一张订单的起始及终止运输城市编号。题目 保证所有编号合法，并且不存在起点和终点重合的情况。

输出

在一行中输出可运输货物的最大重量。

样例输入

10 6

0 7 8 5 2 3 1 9 10

0 9

1 8

2 7

6 3

4 5

4 2

样例输出

7

提示

样例提示： 我们选择执行最后两张订单，即把 5 公斤货从城市 4 运到城市 2，并且把 2 公斤货从城市 4 运到城市 5，就可以得到最大运输量 7 公斤。