최적의 우유 짜기

농부 John이 새로 산 헛간에는 착유기 $N$대가 한 줄로 놓여 있다. 착유기에는 왼쪽부터 차례로 $1$번부터 $N$번까지 번호가 붙어 있다.

$i$번 착유기는 하루에 우유 $M(i)$단위를 짠다. 그런데 착유기를 너무 촘촘하게 설치한 탓에, 어느 날 $i$번 착유기를 가동하면 그날은 바로 옆 착유기를 가동할 수 없다. 양 끝 착유기는 이웃이 하나뿐이다. 가동할 착유기 집합은 날마다 새로 고를 수 있다.

John은 $D$일 동안 짤 수 있는 우유의 최대 총량을 알고 싶다. 매일 아침 John은 착유기 한 대를 정비할 시간이 있고, 그날부터 그 착유기의 하루 생산량 $M(i)$가 바뀐다. 날마다의 정비 내역이 주어질 때, $D$일 동안 짤 수 있는 우유의 최대 총량을 구하라. 이 값은 32비트 정수 범위를 넘을 수 있다.

$1 \le N \le 40000$, $1 \le M(i) \le 100000$, $1 \le D \le 50000$이다.

첫째 줄에 $N$과 $D$가 주어진다.

이어지는 $N$개 줄 가운데 $i$번째 줄에는 $M(i)$의 초기값이 주어진다.

그다음 $D$개 줄 가운데 $d$번째 줄에는 정수 $i$와 $m$이 주어진다. $d$일째 아침에 John이 $M(i)$를 $m$으로 바꾼다는 뜻이다.

첫째 줄에 $D$일 동안 짤 수 있는 우유의 최대 총량을 출력한다.

착유기 5대의 초기 생산량이 차례로 1, 2, 3, 4, 5이고, 첫째 날 아침에 5번 착유기가 2로 바뀌는 경우를 보자.

첫째 날의 최댓값은 $2 + 4 = 6$이고, $1 + 3 + 2$로도 6을 만든다. 이어서 2번 착유기가 7로 바뀌면 둘째 날은 $7 + 4 = 11$, 1번 착유기가 10으로 바뀌면 셋째 날은 $10 + 3 + 2 = 15$이다.