题目描述

某游戏里有一只怪兽，怪兽有初始血量 $b$，玩家可以对怪兽攻击 $n$ 回合，每回合有两种攻击方式：方式一，物理攻击，此回合怪兽损失 $c_i$ 点血量；方式二，法术攻击，本回合怪兽不损失血量，之后每回合都损失 $p_i$ 点血量，且不同回合的法术攻击效果可累加。

$n$ 回合之后，玩家不再攻击，但是法术攻击效果持续直到怪物死亡。

每回合可以选择其中一种攻击方式，请计算怪兽最少可以在多少回合死掉？

输入格式

从文件 fight.in 中读入数据。

总计 $n+1$ 行。

第 $1$ 行两个正整数 $b$ 和 $n$，表示怪物初始血量和攻击回合数。

之后 $n$ 行每行两个数 $c_i$ 和 $p_i$，表示每回合物理攻击和法术攻击的数值。

输出格式

输出到文件 fight.out 中。

一行，一个正整数，表示怪物至少多少回合死亡。

样例 #1

样例输入 #1

100 5
50 10
20 30
20 50
15 10
20 100

样例输出 #1

3

样例输入 #2

443 3
28 10
1 49
74 40

样例输出 #2

7 

提示

【数据范围】

对于 $35\%$ 的数据，有$1\le n \le 10^3，1\le b,c_i,p_i \le 10^7$。

对于 $100\%$ 的数据，有 $1\le n \le 10^5，1\le b,c_i,p_i \le 10^9$。

另外的：保证有20%数据只使用物理攻击可以使怪兽在最少回合死掉。