史蒂夫去服务器的系统商店卖东西。

一个人的背包有21格。

一开始他的背包里有m件不同的物品（不能卖）。（即剩下21-m格可以用来放卖的东西）

他要从家里的n种物品中选择一些放进背包，每种物品有ai件,价值bi,一格可以放ci个，

相同的物品可以放同一格(只要没放满）,不同的物品不可以放同一格。

问他跑一次最多能卖多少钱。

第一行m,n(0<=m<=21,0<=n<=100)；

下面n行 ai,bi,ci(0<=ai<=1344,0<=bi<=10000,0<ci<=64)；

最多卖的钱s；