题目描述

黑猫老师去服务器的系统商店买东西。

黑猫老师的背包有 $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$。

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

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$。