Người anh tham lam

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\). Người anh mang theo một chiếc túi chịu được tổng trọng lượng tối đa \(M\), mỗi hòn vàng chỉ có thể lấy tối đa một lần.

Hãy tìm tổng giá trị lớn nhất của các hòn vàng mà người anh có thể bỏ vào túi mà tổng trọng lượng không vượt quá \(M\).

Input

• Dòng đầu chứa hai số nguyên \(M\) 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 500\)
• \(1 \le M \le 2 \cdot 10^6\)
• \(0 \le w_i \le 10^9\)
• \(0 \le v_i \le 10^9\)
• \(N \cdot \sum_{i=1}^{N} \max(0,\, M - w_i) \le 10^8\) (các hòn vàng nặng hơn \(M\) không đóng góp vào tổng này).

Sample Input

12 4
6 3
9 7
5 4
13 9

Sample Output

19

Explanation

Chọn hòn 2 và hòn 3 (nặng \(7+4=11 \le 12\)) được giá trị \(14\); chọn hòn 1 và hòn 4 (nặng \(3+9=12\)) được \(19\); chọn hòn 1, 2 (nặng \(10\)) được \(15\). Kết quả tốt nhất là \(19\).