测试数据来自 system/1119

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　小H参工作了，在某大厂担任算法工程师。为增加收入，他接到一个软件开发的私活，该软件包含了 \(n\) 个子模块，并且模块是相互关联的，必须按给定的顺序一次完成，比如，模块3必须在模块4之前或同一个月开发出来。

　　由于小H的工资收入是 \(m\) 元每月，但工作繁忙，基本没有时间来完成私活，所以他决定请帮手来完成这个软件。帮手们不是免费的，但他们能保证在一个月内完成任意多个模块。每完成一个模块，小H有两笔支付款：第一笔 \(a_i(1 ≤ a_i ≤ m)\) 元在做该模块的那一个月初支付，第二笔 \(b_i\) 元 \((1 ≤ b_i ≤ m)\) 在完成该模块后的下一个月初支付。 每一个月小H会用上一个月的工资来付款，即每个月小H最多能拿出 \(m\) 元来付款。

　　现在请你帮助小H找出完成所有模块并支付完所有款项的最短月数。

【输入格式】

　　第一行: \(m\) 和 \(n\)，它们的意义如题目描述。
　　接下来的N行，每行包含 \(a_i\) 和 \(b_i\), 分别是完成第 \(i\) 个模块开始钱的付款和完成后的付款.

【输出格式】

　　完成所有模块并付完帐目的最少月数。

【输入输出样例】

　Input

100 5
40 20
60 20
30 50
30 50
40 40

　Output

6

【样例解释】

　　样例中每个月工资为100，那么至少需要6天完成5个模块的开发，具体方案如下：

【数据限制】

　　\(1 \le n \le 300\)，\(1 \le m \le 1000\)

【来源】

　　Mr.he