小明去服务器的系统商店买东西。

一个人的背包有 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。

• 0\leq m\leq 21；
• 0\leq n\leq 100；
• 0\leq a_i\leq 1344；
• 0\leq b_i\leq 10^4；
• 0< c_i \leq 64；
• 0<|st_i|<100；
• 0\leq s\leq 10^6。