Start 2024-04-06 14:20:00

20240406 背包问题一(maoyu)

End 2024-04-13 00:00:00
Contest is over.
Now 2026-11-19 00:33:20

C. 分组背包

Description

物品大致可分为k(k\le100)组,同一组中的物品最多放1个,试求背包能装下的物品的最大价值是多少。

Input

第一行为两个数m(0\le m\le1 000)和n(1\le n\le1 000),表示背包总重量为m,共有n件物品。 接下来n行,每行3个数a_i,b_i,c_i,表示物品的重量,价值和所属组数。

Output

输出一个数,即背包能装下的最大价值。

Examples

Input

46 3
10 10 1
10 6 1
60 300 2

Output

10

Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit