小王祝大家开局开好运

时间限制：1s

空间限制：16MB

Description

$Y$ 王者荣耀是一款风靡全国的$MOBA$手游。游戏里有各种各样的装备，其属性各不相同，价格也都不同。

小王是王者荣耀的萌新玩家，现在正在玩这个游戏，他玩的角色名叫 百里守约 。

角色 百里守约 的攻击不会产生暴击，每 $1$ 点暴击率会转化为 $3$ 点攻击力，角色的基础攻击力为 $220$;

现在他有金币数为$m$，由于他是萌新，不懂怎么买装备，所以他还没有购买任何装备。

他想知道怎么恰当购买装备，使得单次攻击打出的伤害最高。他于是挂机（退出游戏）给你发消息，向你这个编程天才求助。

注意：装备最多买 $6$ 个, 假定是正常出装（即不重复购买装备）。

Input Format

第一行包含两个整数 $m(300 ≤ m ≤ 10^4)$ ，即小王现在有多少金币 ； $n(1 ≤ n ≤ 20)$ ， 即允许购买的装备数量。

以下 $n$ 行，每行包含三个正整数 $a_i$，$b_i$，$c_i$，分别是装备的攻击力、暴击率、价格。

Output Format

输出一个整数，表示小王单次攻击能够打出的最大伤害。

Data Range

• $300 ≤ m ≤ 10^4$
• $1 ≤ n ≤ 20$
• $0 ≤ a_i ≤ 180$，$0 ≤ b_i ≤ 25$, $500 ≤ c_i ≤ 3400$;

Input Example #1：

800 3
80 10 200
100 20 400
80 0 400

Output Example #1：

490