题目内容

某大型商场正在进行优惠大促销，全场每满 200 减 20，如果购买的商品种类大于等于 3 种，则可以每满 200 减 30，两种促销不能叠加。

小明正准备给新家置办生活用品，精心挑选了很多商品，但预算有限，无法全部购买。小明给挑选的商品都打了满意度评分，请帮小明在有限的预算中，挑选出最心仪的商品组合吧。

规则：相同商品最多购买一件，购买的商品总数没有限制。

输入描述

第一行为预算值，取值范围为 $[10, 1000]$。

第二行为待挑选的商品总数，取值范围为 $[1, 20]$。

后续为商品信息，每一行表示一种商品，共 4 列，使用空格隔开，都是正整数：

• 第一列为编号，编号唯一，取值范围：$[10000, 20000]$
• 第二列为类别，不同商品可以归属同一类别，取值范围：$[1, 10]$
• 第三列为价格，取值范围：$[1, 200]$
• 第四列为满意度，取值范围：$[1, 240]$

输出描述

在预算范围内，输出挑选的商品的满意度值之和的最大值。

样例1

输入

100
3
10001 1 100 90
10002 2 100 100
10003 3 100 110

输出

110

说明 第一行为预算值 100，第二行为商品总数 3 个，后面几行为商品信息。所有商品价格都是 100，选择满意度值最大的 10003 号商品，满意度值为 110，故输出为 110。

样例2

输入

200
4
10001 1 200 200
10002 2 10 10
10003 3 10 10
10004 3 10 10

输出

230

说明 第一行为预算值 200，第二行为商品总数 4 个，后面几行为商品信息。单独选择 10001 号商品可以满 200 减 20，还能再添加 10002 和 10003 两件商品；此时又满足 3 个品类的商品满 200-30，还能再选择 10004 号商品。这 4 个商品的总满意度为 $200+10+10+10=230$，故输出为 230。