농부존은 최근에 N 개의 우유기계(milk machines) 가 들어있는 헛간을 하나 샀습니다.(1<= N <= 40000, 첫번째 기계를 1 마지막 기계를 N 이라고 숫자를 붙입시다). i번째 우유기계는 M(i) 단위 만큼의 우유를 하루에 뽑아낼 수 있습니다.(1<= M(i) <= 100,000).

재수없게도, 기계들은 너무 가까이 설치가 되있어서 만약 i번째 기계가 어떤 특정한 날에 가동중이라면 i-1 번째 기계와 i+1 번째 기계는 그날 작동을 할 수 없습니다.(1번 기계와 N번 기계는 단 한개의 이웃한 기계만을 가집니다.) 농부존은 작동을 시킬 기계의 조합을 매일 다르게 바꿀 수 있습니다.

농부존은 D 일동안 뽑아낼 수 있는 우유의 양에 관심이 있습니다.(1<= D <= 50,000). 각날이 시작될 때마다 그는 하나의 선택된 i번째 우유기계를 유지보수를 실시하여 그 기계의 생산량 M(i) 를 그 전날로 부터 변경할 충분한 시간이 있습니다. 매일의 변경 내용이 포함된 리스트가 주어졌을 때, 농부존에게 D 일동안 최대한 얼마나 생산할 수 있는지 알려주시오.(그 양은 32비트 정수로 표현이 불가능 할 수도 있습니다.)

입력

• Line 1: N,D 가 주어집니다.
• Lines 2..1+N: i+1 번째 줄에는 M(i) 의 초기값이 주어집니다.
• Lines 2+N..1+N+D: 1+N+d 번째 줄에는 두개의 정수 i 와 m 이 주어집니다.(이는 농부존이 M(i) 의 값을 m 으로 d번째 날에 변경함을 나타냅니다)

출력

입출력 예

입력 

5 3 
1 
2 
3 
4 
5 
5 2 
2 7 
1 10 

출력 

32 

INPUT DETAILS: 

기계 5개가 있습니다.(초기의 우유생산량은 1,2,3,4,5 입니다.) 
첫날에는 5번째 우유기계는 2 만큼의 우유를 생산하도록 변경되었습니다. 
...등등 

OUTPUT DETAILS: 

첫날에 최적의 생산량은 6입니다.(2+4 = 6 혹은 1+3+2 = 6) 
두번째 날에 최적 생산량은 7+4 = 11 입니다. 
세번째 날은 10+13+2 = 15 입니다. 
따라서 3일동안 최대 생산할 수 있는 양은 15+11 + 6 = 32 입니다.

Milking machine i is capable of extracting M(i) units of milk per day (1 <= M(i) <= 100,000). Unfortunately, the machines were installed so close together that if a machine i is in use on a particular day, its two neighboring machines cannot be used that day (endpoint machines have only one neighbor, of course). Farmer John is free to select different subsets of machines to operate on different days.

Farmer John is interested in computing the maximum amount of milk he can extract over a series of D days (1 <= D <= 50,000). At the beginning of each day, he has enough time to perform maintenance on one selected milking machine i, thereby changing its daily milk output M(i) from that day forward. Given a list of these daily modifications, please tell Farmer John how much milk he can produce over D days (note that this number might not fit into a 32-bit integer).

입력

• * Line 1: The values of N and D.
• * Lines 2..1+N: Line i+1 contains the initial value of M(i).
• * Lines 2+N..1+N+D: Line 1+N+d contains two integers i and m, indicating that Farmer John updates the value of M(i) to m at the beginning of day d.

출력

입출력 예

입력

5 3
1
2
3
4
5
5 2
2 7
1 10

출력

32

INPUT DETAILS:

There are 5 machines, with initial milk outputs 1,2,3,4,5.  On day 1,
machine 5 is updated to output 2 unit of milk, and so on.

OUTPUT DETAILS:

On day one, the optimal amount of milk is 2+4 = 6 (also achievable as
1+3+2).  On day two, the optimal amount is 7+4 = 11.  On day three, the
optimal amount is 10+3+2=15.

출처:usaco/2013/dec/gold
번역:conankun