Người anh và hai túi

Người anh tham lam đến đảo châu báu, trên đảo có \(N\) hòn vàng. Hòn vàng thứ \(i\) nặng \(w_i\) và có giá trị \(v_i\). Lần này người anh mang theo hai chiếc túi, chịu được trọng lượng tối đa lần lượt là \(M_1\) và \(M_2\). Mỗi hòn vàng chỉ được bỏ vào tối đa một túi (hoặc bỏ lại), và tổng trọng lượng trong mỗi túi không được vượt quá sức chịu của túi đó.

Hãy tìm tổng giá trị lớn nhất của các hòn vàng mang đi được.

Input

• Dòng đầu chứa ba số nguyên \(M_1\), \(M_2\) và \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(v_i\) và \(w_i\): giá trị và trọng lượng của hòn vàng thứ \(i\).

Output

In ra một số nguyên duy nhất: tổng giá trị lớn nhất.

Constraints

• \(1 \le N \le 200\)
• \(1 \le M_1, M_2 \le 200\)
• \(0 \le w_i \le 200\)
• \(0 \le v_i \le 200\)

Sample Input 1

9 5 4
10 5
7 4
8 6
3 3

Sample Output 1

21

Sample Input 2

6 6 3
9 4
8 4
5 4

Sample Output 2

17

Explanation

Ví dụ 1: đặt hòn 3 và hòn 4 vào túi 1 (nặng \(6+3=9\), giá trị \(11\)) và hòn 1 vào túi 2 (nặng \(5\), giá trị \(10\)): tổng \(21\). Cách khác, hòn 1 và 2 vào túi 1 và hòn 4 vào túi 2, chỉ được \(20\). Ví dụ 2: mỗi túi chứa được đúng một hòn nặng \(4\) nên chọn hai hòn giá trị \(9\) và \(8\), tổng \(17\).