【mc生存】卖东西

题目背景

服务器好好玩

题目描述

lcy0x1去服务器的系统商店卖东西。 一个人的背包有21格。 一开始他的背包里有m件不同的物品(不能卖)。 他要卖n种物品,每种物品有ai件,价值bi,一格可以放ci个, 名字sti(0<sti的长度<100) 相同的物品可以放同一格(只要没放满)。 问他跑一次最多能卖多少钱。

输入输出格式

输入格式


第一行m,n(0<=m<=21,0<=n<=100); 下面n行 ai,bi,ci,sti(0<=ai<=1344,0<=bi<=10000,0<ci<=64);

输出格式


最多卖的钱s(0<=s<=1000000);

输入输出样例

输入样例 #1

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

输出样例 #1

64

说明

多重背包 搜索0分!!! 强大的数据