DUTUYEN

Tuân là khách quen của tiệm bánh "xyz".Mỗi ngày Tuân đến chủ tiệm lại dọn ra N chiếc bánh (N <= 40000) xếp thành hàng ngang chiếc bánh thứ i có độ ngon là Mi(Mi <= 100000).Tuân mặc dù rất ham ăn nhưng luôn cố tỏ ra nhã nhặn vì vậy cậu không bao giờ ăn hai cái bánh xếp cạnh nhau.Tuân đến ăn bánh trong D ngày (D <= 50000) , vì không muốn Tuân chán nên vào mỗi ngày chủ tiệm quyết định thay đổi chiếc bánh thứ i thành có độ ngon là Ci (Ci <= 100000) . Bạn hãy giúp Tuân tìm ra chiến lược để ăn bánh sao cho tổng độ ngon là lớn nhất.

Input

Dòng đầu là N và D.
N dòng tiếp theo là các số Mi.
D dòng tiếp theo là các số Pi và Ci thể hiện chếc bánh thứ Pi có độ ngon mới là Ci. 

Output

In ra tổng độ ngon tối đa sau D ngày.

Example

Input:

5 3

1

2

3

4

5

5 2

2 7

1 10

Output:
32

Giải thích:
Ngày 1: 1 2 3 4 2 : Đáp số là 6
Ngày 2: 1 7 3 4 2 : Đáp số là 11
Ngày 3: 10 7 3 4 2: Đáp số là 15.