Farmer John vừa mua chuồng mới có $N$ máy vắt ($1 \le N \le 40,000$), đánh số $1..N$ thành hàng.

Máy $i$ vắt $M(i)$ đơn vị mỗi ngày ($1 \le M(i) \le 100{,}000$). Quá gần nhau: nếu dùng $i$ hôm đó thì hai máy kề không được dùng (đầu hàng chỉ một máy kề). Mỗi ngày được chọn tập con khác nhau.

Ông muốn tổng tối đa trong $D$ ngày ($1 \le D \le 50,000$). Đầu mỗi ngày đủ thời gian bảo trì một máy chọn $i$, đổi sản lượng ngày $M(i)$ từ hôm đó về sau. Theo danh sách thay đổi, tìm tổng tối đa trong $D$ ngày (có thể vượt số nguyên 32 bit).

Dữ liệu vào

• Dòng 1: $N$ và $D$.
• Dòng $2..1+N$: dòng $i+1$ chứa $M(i)$ ban đầu.
• Dòng $2+N..1+N+D$: dòng $1+N+d$ có số nguyên $i$, $m$, đổi $M(i)$ thành $m$ đầu ngày $d$.

Dữ liệu ra

• Dòng 1: tổng tối đa FJ vắt trong $D$ ngày.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

32

Ghi chú

5 máy ban đầu 1,2,3,4,5. Ngày 1 máy 5 đổi thành 2 đơn vị, v.v.

Ngày 1 tối ưu $2+4 = 6$ (cũng $1+3+2$); ngày 2 $7+4 = 11$; ngày 3 $10+3+2=15$.

Tác giả bài toán: Brian Dean