【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$ 分,请使用多重背包。**