THỰC HÀNH

Phong Dương vừa được thăng chức làm giám đốc Ngân hàng Nhà nước. Ngân hàng có N máy in tiền xếp thành hàng ngang, đánh số từ 1 tới N theo thứ tự từ trái sang phải.

Máy in tiền thứ có thể in được Mi đồng một ngày. Nhưng không may, các máy in tiền được xếp quá gần nhau nên nếu máy i được sử dụng trong một ngày nào đó thì hai máy kề với máy là hai máy i+1 và i - 1 (hai máy đầu và cuối chỉ có một máy kề) sẽ không sử dụng được trong cùng ngày.

Biết rằng, bắt đầu mỗi ngày, Phong Dương bảo trì một máy in i bất kì, do đó số tiền in được Mi của máy bị thay đổi. Cho trước danh sách những thay đổi, hãy giúp Phong Dương tính số tiền nhiều nhất in được sau D ngày.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số N và D (1 <= N <= 40000; 1 <= D <= 50000);
• N dòng tiếp theo, dòng thứ là Mi (1 <= Mi <= 10^5)
• D dòng tiếp theo, dòng thứ gồm hai số i và m tương ứng vào ngày j thì thay đổi giá trị Mi = m. Các số trên một dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra:

Ghi ra một dòng duy nhất là số tiền thu được nhiều nhất sau D ngày.

Example

Input:
5 3
1
2
3
4
5
5 2
2 7
1 10

Output:
32