Người anh tham lam vô hạn

Người anh tham lam đến đảo châu báu, trên đảo có \(N\) loại vàng, mỗi loại có số lượng không giới hạn. Một thỏi vàng loại \(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\).

Hãy tìm tổng giá trị lớn nhất có thể mang đi, biết rằng mỗi loại có thể lấy bao nhiêu thỏi tuỳ ý (kể cả không lấy) và 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 một thỏi loại \(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\)
• \(1 \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 loại nặng hơn \(M\) không đóng góp vào tổng này).

Sample Input

13 3
6 4
5 3
9 5

Sample Output

23

Explanation

Chọn \(2\) thỏi loại 3 (nặng \(10\), giá trị \(18\)) và \(1\) thỏi loại 2 (nặng \(3\), giá trị \(5\)): tổng nặng \(13\), giá trị \(23\). Đây là phương án tốt nhất.