Để chuẩn bị bánh cho mùa Trung thu sắp đến, Nam mua $N$ lò bánh nướng bánh trung thu, các lò nướng được xếp thành $1$ hàng và đánh số từ $1$ đến $N$. Lò $i$ có khả năng mỗi ngày nướng ra được ~M_i~ cái bánh. Do đặt các lò bánh quá gần nhau nên lò $i$ hoạt động thì hai lò cạnh bên không hoạt động (lò ở hai đầu chỉ có một lò bên cạnh). Nam dự định làm bánh trung thu trong $D$ ngày. Mỗi ngày Nam chọn một số lò để nướng bánh và chọn một lò $j$ bất kì thay đổi số lượng bánh nướng ra được mỗi ngày $M_j$ của lò này.

Yêu cầu: Hãy cho biết số lượng bánh trung thu nhiều nhất mà Nam có thể nướng ra được sau $D$ ngày.

Dữ liệu vào

Vào từ tập tin văn bản MOONCAKE.INP gồm:

• Dòng thứ nhất: Ghi hai số nguyên dương $N$ và $D$, là số lượng lò bánh và số ngày nướng bánh $(1 \le N \le 40\ 000, 1 \le D \le 50\ 000)$
• Dòng thứ $2$ đến dòng thứ $N+1$: Dòng thứ $i+1$ chứa một số nguyên dương là số bánh được nướng ra mỗi ngày ~M_i~ của lò thứ $i \ (1 \le M_i \le 100\ 000)$
• Dòng thứ $N+2$ đến dòng thứ $N+D+1$: Dòng thứ $N+k+1$ chứa hai số nguyên $i$ và $c$ cho biết Nam thay đổi số lượng bánh nướng ra được mỗi ngày của lò $i$ thành $c$ bắt đầu từ ngày $k$

Kết quả ra

Ghi ra tập tin văn bản MOONCAKE.OUT gồm:

• Một số nguyên là số lượng bánh trung thu nhiều nhất làm ra được theo mô tả như trên

Ví dụ $1$

Dữ liệu

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

Kết quả

32

Ví dụ $2$

Dữ liệu

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

Kết quả

39