데이터 처리

외계인 개발자는 최근에 N(1 <= N <= 40,000)개의 고성능 컴퓨터를 포함하는 새로운 데이터 센터를 구축했습니다. 편의상 각 컴퓨터는 1..N 까지 번호가 매겨져 있으며, 한 줄로 배열되어 있습니다.

컴퓨터 i는 하루에 M(i) (1 <= M(i) <= 100,000) 단위의 데이터를 처리할 수 있습니다. 하지만, 컴퓨터들이 서로 너무 가까이 설치되어 있어서 특정한 날에 컴퓨터 i가 작동 중이면, 그 주변의 두 대의 컴퓨터는 그 날 사용할 수 없습니다. (끝에 있는 컴퓨터는 이웃이 하나뿐입니다). 개발자는 다른 날에는 다른 컴퓨터를 작동시킬 수 있습니다.

개발자는 D(1 <= D <= 50,000) 일 동안 최대한 많은 데이터를 처리하고자 합니다. 각 날마다, 그는 선택한  컴퓨터 i에 유지 보수를 할 수 있는 충분한 시간이 있으며, 그로 인해 그 다음 날 이후부터의 데이터 처리 능력 M(i)를 변경할 수 있습니다. 주어진 일일 수정 사항 목록을 기반으로, 개발자가 D 일 동안 처리할 수 있는 데이터의 양을 계산해주세요. (이 숫자는 32비트 정수로 표현할 수 없을 수 있으니 주의하십시오).

• 첫 번째 줄: N과 D의 값
• 두 번째 줄 ~ 1+N 번째 줄 : i+1 번째 줄에는 M(i)의 초기값이 포함됩니다.
• 2+N 번째 줄 ~ 1+N+D 번째 줄 : 1+N+d 줄에는 두 개의 정수 i와 m이 포함되어 있으며, 이는 개발자가 D번째 날부터 M(i)의 값을 m으로 업데이트했음을 의미합니다.

• 첫 번째 줄: 개발자가 D 일 동안 처리할 수 있는 최대 데이터 처리량