题目描述

你有一个容量为 $21$ 格的背包。初始时背包里已有 $m$ 件不同的物品，它们各自占据一个格子且不能出售，因此你只剩下 $21 - m$ 个空格可以使用。

现在你可以购买 $n$ 种物品。每种物品用一个字符串 $st_i$ 作为名称，并且有：

• $a_i$：该种物品最多可购买的数量（库存）；
• $b_i$：单件物品的价值；
• $c_i$：同一个格子最多能堆叠的数量。

相同名称的物品被视为同一种，实际可购买总量为所有同名物品的 $a_i$ 之和，单件价值和堆叠数量保证在输入中同名物品完全一致。
同一种物品可以放进同一个格子，只要不超过 $c_i$ 件。不同种的物品不能放在同一格。

你需要决定购买哪些物品、数量各多少，使得总价值最大，并且所有物品能完全放入剩余的 $21-m$ 个格子中。求最大总价值 $s$。

输入格式

第一行两个整数 $m, n$，表示已占格子数和可购买物品种类数。

接下来 $n$ 行，每行包括三个整数 $a_i, b_i, c_i$ 和一个字符串 $st_i$，分别表示该种物品的库存、单件价值和单格堆叠上限。字符串不包含空格。

输出格式

一个整数，表示能买到的最大总价值。

样例

20 3
63 1 64 yinshifen
1 10 1 men
1 1 64 yinshifen

64

样例解释
剩余 $1$ 个空格。yinshifen 库存共 $64$，可在一个格子里堆叠 $64$ 件，总价值 $64$；men 价值 $10$。显然选择 yinshifen 获得 $64$ 最优。

数据范围

• $0 \le m \le 21$
• $1 \le n \le 1000$
• $0 \le a_i \le 1000$（库存可能为 $0$，表示无法购买）
• $0 \le b_i \le 10^5$（价值可能为 $0$）
• $1 \le c_i \le 100$
• 字符串长度 $\le 20$，由小写字母组成
• 保证输入中同名物品的 $b_i, c_i$ 相同