#1147. MONEY - Máy in tiền

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ó máy in tiền xếp thành hàng ngang, đánh số từ tới theo thứ tự từ trái sang phải.

Máy in tiền thứ có thể in được đồ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 được sử dụng trong một ngày nào đó thì hai máy kề với máy là hai máy và (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 bất kì, do đó số tiền in được 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 ngày.

Dữ liệu vào:

• Dòng đầu tiên chứa hai số và ;
• dòng tiếp theo, dòng thứ là ;
• dòng tiếp theo, dòng thứ gồm hai số và , tương ứng vào ngày thì thay đổi giá trị . 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 ngày.

Ví dụ:

Dữ liệu vào:

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

Dữ liệu ra:

32

Giải thích:

• Vào ngày , theo thứ tự, số tiền in được ở các máy: , vậy số tiền thu được nhiều nhất: (hoặc ).
• Ngày , theo thứ tự, số tiền in được ở các máy: , vậy số tiền thu được nhiều nhất: .
• Ngày , theo thứ tự, số tiền in được ở các máy: , vậy số tiền thu được nhiều nhất: .
• Vậy tổng số tiền sau ngày: .

Giới hạn:

• số điểm có .