小明去服务器的系统商店买东西。
一个人的背包有 21 格。
一开始他的背包里有 m 格不同的物品（不能卖）。
他在 n 种物品选择购买，第 i 件物品的名字为 st_i，有 a_i 件，价值为 b_i，这种物品一格可以放 c_i 个。
商店的物品名字相同，那么就是同一种类的物品。
相同种类的物品可以放同一格（只要没放满）。
问：背包最多装多少价值总和的物品（除哪些不能卖的物品之外）
第一行两个整数 m,n。
下面 n 行，第 i+1 行三个整数 a_i,b_i,c_i 与一个字符串 st_i。
最多卖的钱 s。
20 3 63 1 64 yinshifen 1 10 1 men 1 1 64 yinshifen
64