Huy là một thợ lặn và một thợ săn kho báu. Anh ta vừa tìm thấy vị trí của một con tàu cướp biển chứa đầy kho báu. Hệ thống sonar tinh vi trên tàu cho phép anh ta xác định vị trí, độ sâu và số lượng vàng trong mỗi kho báu. Không may mắn, Huy quên mang theo thiết bị GPS và cơ hội bao giờ tìm thấy vị trí này một lần nữa rất mỏng nên anh ta phải lấy vàng ngay bây giờ. Huy chỉ có một chai khí nén. Huy muốn lặn với chai khí nén để thu hồi càng nhiều vàng càng tốt từ xác tàu.

Viết chương trình Huy có thể sử dụng để chọn kho báu nào anh ta nên chọn để tối đa hóa số lượng vàng phục hồi. Vấn đề có những hạn chế như sau:

• Có \(n\) kho báu \((d_1,v_1),(d_2,v_2),...(d_n,v_n)\) được đại diện bởi cặp (độ sâu, số lượng vàng). Có tối đa \(30\) báu vật.
• Bình khí chỉ cho phép \(t\) giây dưới nước, \(t\) nhiều nhất là \(1000\) giây.
• Trong mỗi lần lặn, Huy có thể mang tối đa \(1\) kho báu mỗi lần.
• Thời gian lặn xuống độ xâu \(d_i\) là \(d_i \times w\) trong đó \(w\) là hằng số nguyên.
• Thời gian đi từ độ xâu lên \(d_i\) mặt nước là \(2 \times d_i \times w\), trong đó \(w\) là hằng số nguyên.
• Do giới hạn dụng cụ, tất cả các tham số là số nguyên.

Dữ liệu vào

• Đầu vào chứa một số trường hợp thử nghiệm. Dòng đầu tiên của mỗi tập dữ liệu phải chứa các giá trị \(t\) và \(w\). Dòng thứ hai chứa số \(n\) - số lượng kho báu. Mỗi dòng sau đây chứa độ sâu \(d_i\) và số lượng vàng \(v_i\) khác nhau của \(n\) kho báu.
• Một dòng trống ngăn cách các trường hợp thử nghiệm.

Dữ liệu ra

• In ra nhiều dòng, mỗi dòng là số lượng vàng tối đa thu hồi được.

Input 1

210 4
3
10 5
10 1
7 2

Output 1

7

Giải thích

Chai khí nén có công suất 210 giây, hằng số \(w\) có giá trị 4 và có 3 báu vật, cái đầu tiên ở độ sâu 10 mét và trị giá 5 đồng vàng, cái thứ hai ở độ sâu 10 mét và trị giá 1 đồng vàng, và cái thứ ba ở độ cao 7 mét và trị giá 2 đồng vàng.