[Usaco2007 Jan]Problem Solving 解题

农夫 John 的奶牛们需要依次解决 $P$ 道题目，其中 $1\le P\le 300$。与此同时，它们像普通人一样外出工作，每个月可以获得 $M$ 元工资，其中 $1\le M\le 1000$。

这些题目非常困难，因此奶牛们需要雇用助手。助手可以保证在一个月内解决任意一道题目。解决第 $i$ 道题目需要分两次付款：

• 在开始解决该题目的当月月初支付 $A_i$ 元；
• 在该题目完成后的下一个月月初支付 $B_i$ 元。

其中，$1\le A_i\le M$，$1\le B_i\le M$。

每个月月初，奶牛们只能使用上个月获得的工资付款。它们不会储蓄，每个月没有用完的钱都会被拿去买糖，因此不能留到以后使用。

题目之间存在先后关系，必须按照编号顺序解决。具体来说，对于任意 $i<j$，第 $i$ 道题目必须不晚于第 $j$ 道题目完成；多道连续编号的题目可以在同一个月内解决。

请计算奶牛们解决全部题目并付清所有款项所需的最少月数。

输入格式

第一行输入两个整数 $M$ 和 $P$，分别表示奶牛们每个月的工资和题目数量。

接下来 $P$ 行，第 $i$ 行输入两个整数 $A_i$ 和 $B_i$，分别表示第 $i$ 道题目的预付款和完成后的付款。

输出格式

输出一个整数，表示奶牛们解决全部题目并付清所有款项所需的最少月数。

样例输入

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

样例输出

6

数据范围

• $1\le P\le 300$；
• $1\le M\le 1000$；
• 对于每道题目 $i$，满足 $1\le A_i\le M$，$1\le B_i\le M$。

来源与许可

本题为 USACO 2007 January 试题「Problem Solving」，题面与测试数据整理自 BZOJ。

样例 1

输入

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

输出

6