【mc生存】卖东西
题目背景
服务器好好玩。
题目描述
lcy0x1 去服务器的系统商店买东西。
一个人的背包有 $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$。
输入输出样例
输入样例 #1
20 3
63 1 64 yinshifen
1 10 1 men
1 1 64 yinshifen输出样例 #1
64说明
数据保证：
- $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$。
**注：数据强大，搜索 $0$ 分，请使用多重背包。**