题目描述

小婷和小泽在旅行途中遇到了一只怪物。怪物能够承受 $H$ 点伤害，当他们对怪物累计造成的伤害大于等于 $H$ 时，怪物就会被消灭。

小婷和小泽携带了 $n$ 种炼金道具。第 $i$ 种道具具有耐久 $q_i$、基础伤害 $d_i$ 和特性 $t_i$。每使用一次该道具，都会对怪物造成伤害，并使该道具的耐久减少 $1$。耐久变为 $0$ 后，该道具消失，不能继续使用。

道具可能具有以下两种特性：

• 数量优势： 设使用道具前的剩余耐久为 $r$，本次攻击增加 $r\times 15\%$ 的基础伤害，即本次攻击造成 $d_i\times(1+0.15\times r)$ 点伤害。
• 最后一击： 如果使用道具前的剩余耐久恰好为 $1$，本次攻击增加 $50\%$ 的基础伤害。

如果一种道具同时具有两种特性，则两个加成比例直接相加。例如，一种基础伤害为 $100$、当前剩余耐久为 $1$ 的道具同时具有两种特性，本次攻击造成 $100\times(1+0.15+0.5)=165$ 点伤害。

$t_i$ 与道具特性的对应关系如下：

每次攻击时，小婷和小泽可以选择任意一种耐久大于 $0$ 的道具使用。请计算消灭怪物最少需要使用多少次道具。

输入格式

第一行，两个正整数 $H,n$，分别表示怪物能够承受的伤害和道具种数。

接下来 $n$ 行，每行三个整数 $q_i,d_i,t_i$，分别表示第 $i$ 种道具的初始耐久、基础伤害和特性。

输出格式

如果能够消灭怪物，输出一个正整数，表示最少需要使用的道具次数。

如果用光所有道具仍不能消灭怪物，输出一行字符串 Game Over。

输入

211 3
1 60 2
4 40 3
2 60 0

输出

3

输入

1100 2
2 520 0
2 500 2

输出

2

输入

1000 2
2 100 1
1 200 3

输出

Game Over

说明/提示

样例 $1$ 说明：

一种使用三次道具的方法如下：

第一次使用第 $1$ 种道具。此时剩余耐久为 $1$，最后一击生效，造成 $60\times(1+0.5)=90$ 点伤害。

第二次使用第 $2$ 种道具。此时剩余耐久为 $4$，数量优势生效，造成 $40\times(1+0.15\times4)=64$ 点伤害。

第三次使用第 $3$ 种道具，造成 $60$ 点伤害。三次攻击共造成 $214$ 点伤害，任意两次攻击造成的总伤害都小于 $211$，因此答案为 $3$。

样例 $2$ 说明：

连续两次使用第 $2$ 种道具，造成的伤害分别为 $500$ 和 $500\times(1+0.5)=750$，总伤害为 $1250$。

注意，如果每次都选择当前伤害最大的道具，前两次会选择第 $1$ 种道具，只能造成 $1040$ 点伤害，反而需要进行第三次攻击。

样例 $3$ 说明：

用光第 $1$ 种道具可以造成 $130+115=245$ 点伤害；第 $2$ 种道具可以造成 $200\times(1+0.15+0.5)=330$ 点伤害。所有道具总共只能造成 $575$ 点伤害，无法消灭怪物。

数据范围

本题共 $20$ 个测试点，每个测试点 $5$ 分。各测试点的数据范围如下：

对于 $100\%$ 的数据保证：$1\le H\le 10^9$，$1\le n\le 500$，$1\le q_i\le 20$，$20\le d_i\le 10^9$，$0\le t_i\le 3$。

保证所有 $d_i$ 都是 $20$ 的倍数，因此每次攻击造成的伤害均为整数。