题目背景

服务器好好玩

题目描述

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)；

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

64

提示

多重背包

搜索0分！！！

强大的数据