PROGRAMMING:Sensen Express
Morimori opened an express company, called morimori express. Because the company has just opened, the business route is very simple. It can be considered as a straight line of $$n $$cities, which are numbered from 0 to $$(n-1) $$from left to right. Due to road restrictions, the weight of goods transported between City No. $$I $$($$I = 0, cdots, n-2 $) and City No. $$(I + 1) $) can not exceed $$C at the same time_ I $$kg.
Soon after the company opened, it received $$q $$orders, among which $$J $$orders described that some specified goods should be purchased from $$s_ Transport from city J to city t_ City J $$. Here we simply assume that all goods have unlimited sources, and Sensen will select some of them for transportation from time to time. For the sake of safety, the goods will not be unloaded in the middle of the journey.
In order to make the overall benefit of the company better, Sensen wants to know how to arrange the transportation of the order, so that the weight of the goods transported can be maximized and meet the limit of the road? It should be noted that the delivery time may be at any time, so when we arrange the order, we must ensure that the total weight of all trucks sharing the same road is not overloaded. For example, if we arrange the transportation of two orders from city 1 to city 4 and from city 2 to city 4, the transportation of these two orders is restricted by two roads 2-3 and 3-4 at the same time, because the goods of two orders may be transported on these roads at the same time.
###Input format:
Enter two positive integers, $$n $$and $$q $$($$2 / Le n / Le 10 ^ 5 $$, $$1 / Le Q / Le 10 ^ 5 $$) in the first line, indicating the total number of cities and the order quantity.
The second line gives the number of $$(n-1) $, which in turn represents the maximum allowable freight weight of the road between two adjacent cities $$C_ i$$（$$i=0, \cdots , N-2$$）。 The title guarantees each $$C_ I $$is a non negative integer that does not exceed $$2 ^ {31} $.
Next, $$q $$lines, each line gives the starting and ending transportation city number of an order. The title ensures that all numbers are legal, and there is no overlap between the starting point and the ending point.
###Output format:
Output the maximum weight of transportable goods in one line.
###Input example:
```in
10 6
0 7 8 5 2 3 1 9 10
0 9
1 8
2 7
6 3
4 5
4 2
```
###Output example:
```out
seven
```
###Example prompt: we choose to execute the last two orders, that is, to transport 5kg goods from city 4 to city 2, and to transport 2kg goods from city 4 to city 5, then we can get the maximum transportation volume of 7kg< br>
answer：If there is no answer, please comment
Soon after the company opened, it received $$q $$orders, among which $$J $$orders described that some specified goods should be purchased from $$s_ Transport from city J to city t_ City J $$. Here we simply assume that all goods have unlimited sources, and Sensen will select some of them for transportation from time to time. For the sake of safety, the goods will not be unloaded in the middle of the journey.
In order to make the overall benefit of the company better, Sensen wants to know how to arrange the transportation of the order, so that the weight of the goods transported can be maximized and meet the limit of the road? It should be noted that the delivery time may be at any time, so when we arrange the order, we must ensure that the total weight of all trucks sharing the same road is not overloaded. For example, if we arrange the transportation of two orders from city 1 to city 4 and from city 2 to city 4, the transportation of these two orders is restricted by two roads 2-3 and 3-4 at the same time, because the goods of two orders may be transported on these roads at the same time.
###Input format:
Enter two positive integers, $$n $$and $$q $$($$2 / Le n / Le 10 ^ 5 $$, $$1 / Le Q / Le 10 ^ 5 $$) in the first line, indicating the total number of cities and the order quantity.
The second line gives the number of $$(n-1) $, which in turn represents the maximum allowable freight weight of the road between two adjacent cities $$C_ i$$（$$i=0, \cdots , N-2$$）。 The title guarantees each $$C_ I $$is a non negative integer that does not exceed $$2 ^ {31} $.
Next, $$q $$lines, each line gives the starting and ending transportation city number of an order. The title ensures that all numbers are legal, and there is no overlap between the starting point and the ending point.
###Output format:
Output the maximum weight of transportable goods in one line.
###Input example:
```in
10 6
0 7 8 5 2 3 1 9 10
0 9
1 8
2 7
6 3
4 5
4 2
```
###Output example:
```out
seven
```
###Example prompt: we choose to execute the last two orders, that is, to transport 5kg goods from city 4 to city 2, and to transport 2kg goods from city 4 to city 5, then we can get the maximum transportation volume of 7kg< br>
answer：If there is no answer, please comment