Bánh thiết kế chơi trò tung đồng xu lần, và phụ thuộc vào hai mặt của đồng tiền:
Nếu ngửa sẽ nhận được 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 , nếu tung mặt ngửa thì bộ đếm tăng lên , nếu mặt sấp thì bộ đếm về cho mỗi lần tung. Ngoài ra Bánh thê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 là giá trị thưởng .
Tìm số tiền thưởng lớn nhất mà trò chơi có thể nhận được sau lần tung đồng tiền với các giá trị cho trước.
Input
Dòng thứ nhất chứa hai số nguyên thỏa .
Dòng tiếp theo mỗi dòng chứa phần tử tiền thưởng của các lần thảy xu thỏa .
dòng tiếp theo, mỗi dòng chứa hai số nguyên 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 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: . Nếu các lần tung đồng xu đều ngửa hết, ta có: không đạt max
Comments