Farmer John은 최근 $N$대 착유기($1 \le N \le 40,000$)가 있는 새 헛간을 샀습니다. 번호 $1..N$으로 한 줄입니다.

기계 $i$는 하루 $M(i)$단위($1 \le M(i) \le 100{,}000$)를 짭니다. 너무 가까워 $i$를 쓰는 날은 양옆을 못 씁니다(끝은 물론 이웃 하나). 날마다 다른 부분집합을 선택할 수 있습니다.

$D$일($1 \le D \le 50,000$) 동안 최대 총량을 구합니다. 매일 시작에 한 기계 $i$를 정비해 그날부터 계속 일일 생산 $M(i)$를 바꿀 시간이 있습니다. 변경 목록에서 $D$일 최대량을 구하세요(32비트 정수에 안 들어갈 수 있습니다).

입력

• 1번째 줄: $N$, $D$.
• $2..1+N$번째 줄: $i+1$번째 줄은 초기 $M(i)$.
• $2+N..1+N+D$번째 줄: $1+N+d$번째 줄의 정수 $i$, $m$은 $d$일 시작에 $M(i)$를 $m$으로 바꿉니다.

출력

• 1번째 줄: $D$일 FJ의 최대 총량.

예제

입력 1

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

출력 1

32

참고

5대 초기 생산 1,2,3,4,5입니다. 1일에 기계 5를 2단위로 바꾸는 식입니다.

1일 최적 $2+4 = 6$($1+3+2$도 가능), 2일 $7+4 = 11$, 3일 $10+3+2=15$입니다.

문제 작성자: Brian Dean