Một người nội trợ vừa nhận được phần thưởng được "mua sắm miễn phí miễn là giỏ hàng chưa đầy" tại một cửa hàng bách hóa.

Người này được phát một giỏ hàng có thể mang tối đa ~S~ kilogram. Trong cửa hàng có ~N~ loại mặt hàng. Loại thứ ~i~ có giá trị ~V_i~ SGD, nặng ~W_i~ kilogram và có ~K_i~ bản sao giống hệt nhau.

Hãy chọn các món hàng sao cho tổng khối lượng không vượt quá ~S~ và tổng giá trị là lớn nhất.

Input

Dữ liệu vào từ standard input.

• Dòng đầu tiên chứa hai số nguyên dương ~S~ và ~N~.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~V_i~, ~W_i~, ~K_i~: giá trị, khối lượng và số lượng của loại hàng thứ ~i~.

Output

In ra một số nguyên duy nhất: tổng giá trị lớn nhất (tính theo SGD) có thể lấy được sao cho tổng khối lượng không vượt quá ~S~.

Giới hạn

Thời gian chạy tối đa: ~1.0~ giây.

Với mọi subtask:

• ~1 \le S \le 2000~
• ~1 \le V_i \le 1\,000\,000~
• ~1 \le W_i \le S~

Ví dụ 1

Input

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

Output

15

Giải thích

Có thể lấy một món thuộc mỗi loại ~2~, ~3~, ~4~, ~5~. Tổng khối lượng là ~1 + 4 + 1 + 2 = 8~, tổng giá trị là ~2 + 10 + 1 + 2 = 15~.

Ví dụ 2

Input

20 3
5000 15 1
100 1 3
50 1 4

Output

5400

Giải thích

Có thể lấy một món loại ~1~, ba món loại ~2~ và hai món loại ~3~. Tổng khối lượng là ~15 \times 1 + 1 \times 3 + 1 \times 2 = 20~, tổng giá trị là ~5000 \times 1 + 100 \times 3 + 50 \times 2 = 5400~.

Nguồn

NOI 2018, National Olympiad in Informatics, Singapore - Preliminary Round, Task 2.