Thợ lặn tìm vàng

Một thợ lặn phát hiện một xác tàu đắm có \(n\) kho báu. Kho báu thứ \(i\) nằm ở độ sâu \(d_i\) và chứa \(v_i\) đồng vàng. Bình khí nén chỉ đủ cho \(t\) giây dưới nước cho toàn bộ chuyến đi. Mỗi lần lặn, thợ lặn chỉ mang được tối đa một kho báu, và mỗi kho báu chỉ lấy một lần.

Với hằng số nguyên \(w\), thời gian lặn xuống độ sâu \(d\) mất \(d \cdot w\) giây, còn thời gian bơi từ độ sâu \(d\) lên mặt nước mất \(2 \cdot d \cdot w\) giây. Như vậy lấy kho báu thứ \(i\) tốn tổng cộng \(3 \cdot d_i \cdot w\) giây. Tổng thời gian của các lần lặn không được vượt quá \(t\) (thời gian mất trên mặt nước bỏ qua).

Hãy tìm tổng số vàng lớn nhất thợ lặn có thể thu về.

Input

Gồm nhiều bộ dữ liệu cho đến hết file, mỗi bộ có dạng:

• Dòng đầu chứa hai số nguyên \(t\) và \(w\).
• Dòng thứ hai chứa số nguyên \(n\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(d_i\) và \(v_i\).

Các bộ dữ liệu có thể được ngăn cách nhau bởi các dòng trống. Số bộ dữ liệu không vượt quá \(50\).

Output

Với mỗi bộ dữ liệu in ra một dòng chứa số vàng lớn nhất thu được.

Constraints

• \(1 \le t \le 1000\), \(1 \le w \le 100\)
• \(1 \le n \le 30\)
• \(1 \le d_i \le 1000\)
• \(0 \le v_i \le 1000\)

Sample Input

100 2
4
5 10
3 4
4 6
8 3

60 5
2
2 5
1 1

Sample Output

20
6

Explanation

Bộ 1: chi phí thời gian của các kho báu là \(30, 18, 24, 48\). Chọn kho \(1\), \(2\) và \(3\) tốn \(72 \le 100\) giây và được \(20\) đồng vàng; thêm kho 4 thì vượt quá. Bộ 2: chi phí là \(30\) và \(15\); tổng \(45 \le 60\) nên lấy cả hai, được \(6\) đồng vàng.