当前没有测试数据。

题目描述

辰辰是一位采药人，他每天都要到山里采药。山里的药材种类繁多，每种药材都有其独特的价值和采集特点。

今天，辰辰的背包容积为 V，他有 n 种药材可以选择采集。但这 n 种药材的采集规则各不相同：

• 普通药材：每种只有一株，采或不采（01背包）
• 常见药材：数量无限，想采多少采多少（完全背包）
• 稀有药材：每种有限定数量，最多采指定株数（多重背包）

辰辰想知道，在不超过背包容积的前提下，他最多能获得多少价值的药材？

输入格式

第一行两个整数 V 和 n，分别表示背包的容积和药材的种类数。

接下来 n 行，每行描述一种药材：

• 第一个整数 type 表示药材类型（1=普通，2=常见，3=稀有）
• 第二个整数 w 表示该药材占用的容积
• 第三个整数 v 表示该药材的价值
• 如果 type=3，第四个整数 k 表示该药材的最大采集数量

输出格式

一个整数，表示能获得的最大价值。

样例输入

10 5
1 2 3
2 3 4
3 1 2 3
1 5 10
3 2 5 2

样例输出

21

数据范围

对于 30% 的数据：V ≤ 100, n ≤ 20 对于 60% 的数据：V ≤ 1000, n ≤ 100 对于 100% 的数据：V ≤ 2000, n ≤ 500，每种药材的容积和价值均不超过 1000

提示

这是一道混合背包问题，需要综合运用三种背包的处理方式。

对于普通药材（01背包）：倒序枚举容积。 对于常见药材（完全背包）：正序枚举容积。 对于稀有药材（多重背包）：可以用二进制优化。