Tiếng đồn hai vợ chồng người em thốt nhiên giàu có bay đến tai hai vợ chồng người anh. Hai vợ chồng người anh vội vã đến chỗ nhà em để dò xét. Nghe em thật thà kể chuyện, người anh gạ đổi hết tài sản của mình để lấy túp lều tranh và cây khế. Hai vợ chồng chỉ lo người em không chịu đổi, không ngờ người em vui vẻ ưng thuận ngay.

Hai vợ chồng người anh mừng rỡ như mở cờ trong bụng, lập tức giao hết tài sản của mình cho em, và sáng hôm sau dọn ngay đến ở túp lều tranh trên mảnh vườn nhỏ có cây khế ngọt. Đến ở mảnh vườn chật hẹp, hai vợ chồng người anh không làm việc gì cả. Còn được ít tiền hai vợ chồng đem tiêu dần, cả ngày chỉ nằm khểnh ngoài hè, hí hửng nhìn lên cây khế, chờ chim bay đến. Một buổi sáng, có một luồng gió mạnh tạt vào nhà, rồi hai vợ chồng thấy ngọn cây khế rung chuyển. Hai người hớt hải chạy ra sân, vội nhìn lên cây thì quả nhiên thấy một con chim lớn đang ăn khế.

Như đã hẹn trước, chim thần chở người anh đến đảo châu báu. Trên đảo có \(N\) loại vàng, loại thứ \(i\) có trọng lượng là \(w_i\) và có giá trị là \(v_i\). Người anh tham lam hơn nên đem theo cái túi trăm gang có thể chứa được trọng lượng tối đa là \(M\). Hỏi tổng giá trị tối đa mà người anh có thể lấy là bao nhiêu?

Dữ liệu vào

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

Dữ liệu ra

• Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất người anh có thể lấy được.

Ràng buộc

• \(1 \le N \le 500\)
• \(1 \le M \le 2 \times 10^6\)
• \(0 \le v_i, w_i \le 10^9\)
• \(1 \le N \times \sum_{i=1}^{N} (M - W_i) \le 10^8 \)

Input 1

10 3
7 3
8 8
4 6

Output 1

21