Sau khi chiến thắng chương trình Hãy chọn giá đúng, Amous nhận được phần thưởng là một thẻ mua hàng đặc biệt tại trung tâm thương mại NH. Khi sử dụng thẻ này, bạn sẽ nhận được một xe đẩy lớn để mua hàng, tất cả hàng hóa được bỏ vào trong xe đẩy này sẽ được miễn phí hoàn toàn khi thanh toán.

Chiếc xe đẩy đặc biệt này có sức chứa cân nặng tối đa là \(S\). Trong trung tâm thương mại NH có tất cả \(n\) mặt hàng khác nhau, mặt hàng thứ \(i\) có giá trị là \(v_i\), cân nặng \(w_i\) và có số lượng là \(t_i\) (với cùng giá trị và cân nặng).

Sau khi có được tấm thẻ, vanhthanhthien liền rủ Amous đi mua sắm vào cuối tuần này, cô muốn tìm cách chọn các mặt hàng sao cho tổng giá trị thu được là lớn nhất. Amous dù rất muốn chiều lòng bạn gái nhưng anh đã quá mệt mỏi sau một chuỗi drama dài tuần vừa qua, đành nhờ đến sự giúp đỡ của các bạn chuyên Tin rồi. Hãy giúp anh ấy nhé!

Input

• Dòng đầu chứa hai số nguyên dương \(S,\ n\);
• Tiếp theo là \(n\) dòng, dòng thứ \(i\) chứa ba số nguyên dương \(v_i,\ w_i\) và \(t_i\), lần lượt thể hiện giá trị, cân nặng và số lượng của mặt hàng thứ \(i\).

Output

• In ra một số nguyên dương duy nhất là tổng giá trị của các mặt hàng lớn nhất có thể thu được, sao cho tổng khối lượng không được vượt quá \(S\).

Ví dụ

Sample input 1

15 5
4 12 1
2 1 1
10 4 1
1 1 1
2 2 1

Sample output 1

15

Note

Phương án tối ưu là chọn các vật phẩm thứ \(2,\ 3,\ 4,\ 5\) với tổng cân nặng là \(1 + 4 + 1 + 2 = 8 < 15\), và tổng giá trị thu được là \(2 + 10 + 1 + 2 = 15\).

Sample input 2

20 3
5000 15 1
100 1 3
50 1 4

Sample output 2

5400

Note

Phương án tối ưu là chọn \(1\) vật phẩm thứ nhất, \(3\) vật phẩm thứ hai và \(2\) vật phẩm thứ \(3\). Khi đó tổng khối lượng là \(1\times15 + 3\times1 + 2\times1 = 20\) và tổng giá trị thu được là \(1\times5000 + 3\times100 + 2\times50 = 5400\).

Ràng buộc:

• Trong tất cả subtasks: \(1\leq S\leq2000,\ 1\leq v_i\leq10^6,\ 1\leq w_i\leq S\);
• Subtask 1 (\(8\%\)): \(n = 1,\ 1\leq t_i\leq10^9\);
• Subtask 2 (\(20\%\)): \(1\leq n\leq 100,\ t_i=1\);
• Subtask 3 (\(20\%\)): \(1\leq n\leq 100,\ 1\leq t_i\leq10\);
• Subtask 4 (\(20\%\)): \(1\leq n\leq 500,\ 1\leq t_i\leq10^9\);
• Subtask 5 (\(32\%\)): \(1\leq n\leq 10^5,\ 1\leq t_i\leq10^9\);