Farmer John vừa mua một chuồng bò mới có \(N\) máy vắt sữa (\(1 \le N \le 40\,000\)), được đánh số thuận tiện từ \(1\) đến \(N\) và xếp thành một hàng.

Máy vắt sữa \(i\) có thể lấy được \(M(i)\) đơn vị sữa mỗi ngày (\(1 \le M(i) \le 100\,000\)). Không may, các máy được lắp quá sát nhau nên nếu máy \(i\) được sử dụng trong một ngày nào đó thì hai máy kề nó không thể được sử dụng trong ngày ấy; dĩ nhiên, các máy ở hai đầu chỉ có một máy kề. Farmer John có thể chọn các tập máy khác nhau để vận hành vào những ngày khác nhau.

Farmer John muốn tính lượng sữa lớn nhất có thể lấy được trong \(D\) ngày (\(1 \le D \le 50\,000\)). Vào đầu mỗi ngày, ông có đủ thời gian để bảo trì một máy vắt sữa \(i\) được chọn, qua đó thay đổi sản lượng sữa hằng ngày \(M(i)\) của máy kể từ ngày đó trở đi. Với danh sách các thay đổi hằng ngày này, hãy cho Farmer John biết ông có thể sản xuất bao nhiêu sữa trong \(D\) ngày. Lưu ý rằng kết quả có thể không vừa trong một số nguyên \(32\) bit.

Dữ liệu vào

• Dòng đầu tiên chứa \(N\) và \(D\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa giá trị ban đầu của \(M(i)\).
• \(D\) dòng cuối, dòng thứ \(d\) chứa hai số nguyên \(i\) và \(m\), cho biết Farmer John cập nhật \(M(i)\) thành \(m\) vào đầu ngày \(d\).

Ràng buộc

• \(1 \le N \le 40\,000\).
• \(1 \le M(i) \le 100\,000\).
• \(1 \le D \le 50\,000\).

Dữ liệu ra

In ra tổng lượng sữa lớn nhất Farmer John có thể sản xuất trong \(D\) ngày.

Ví dụ

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

32

Nguồn

USACO 2013 December Contest, Gold — Problem 2: Optimal Milking

Tác giả: Brian Dean, 2013.