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

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