【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

样例输入 #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$ 分，请使用多重背包。