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。

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