Bánh thiết kế chơi trò tung đồng xu ~n~ lần, và phụ thuộc vào hai mặt của đồng tiền:

• Nếu ngửa sẽ nhận được ~x_i~ tiền.

• Nếu sấp sẽ không nhận được đồng nào.

Tuy nhiên để tăng thêm hấp dẫn cho trò chơi, Bánh dùng thêm 1 bộ đếm với khởi tạo ban đầu ~c = 0~, nếu tung mặt ngửa thì bộ đếm tăng lên ~1~, nếu mặt sấp thì bộ đếm về ~0~ cho mỗi lần tung. Ngoài ra Bánh thêm ~m~ phần thưởng thêm vào tương ứng với mỗi giá trị của bộ đếm nếu liên tục được mặt ngửa ~c_i~ là giá trị thưởng ~b_i~.

Tìm số tiền thưởng lớn nhất mà trò chơi có thể nhận được sau ~n~ lần tung đồng tiền với các giá trị ~x_i, c_i~ cho trước.

Input

Dòng thứ nhất chứa hai số nguyên ~n, m~ thỏa ~1\le m \le n \le5000~.

Dòng tiếp theo mỗi dòng chứa ~n~ phần tử tiền thưởng của các lần thảy xu thỏa ~1\le x_i \le 10^9~.

~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~c_i, b_i~ là giá trị tiền thưởng tương ứng với giá trị của bộ đếm.

Output

In ra số tiền thưởng lớn nhất có thể nhận được.

Samples

Sample Input 1

6 3
2 7 1 8 2 8
2 10
3 1
5 5

Sample Output 1

48

Sample Input 2

3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

Sample Output 2

5000000000

Note

Ở testcase ~1~ ta có: Giả sử các lần tung đồng xu đạt ngửa, ngửa, sấp, ngửa, ngửa, ngửa, theo thứ tự này, các khoản tiền sau đây được thưởng và ta nhận được tổng cộng: ~2+(7+10)+0+8+(2+10)+(8+1) = 48~. Nếu các lần tung đồng xu đều ngửa hết, ta có: ~2 + (7 + 10) + (1 + 1) + 8 + (2 + 5) + 8 = 44~ không đạt max