题目描述

在经济比较好的时候，农夫约翰的奶牛没有问题。但是现在，他们有很多问题，很多问题；他们有P(1 ≤ P ≤ 300)个问题。他们已经停止提供牛奶，并像所有其他好公民一样从事正规工作。事实上，在一个正常的月份，他们赚了M(1 ≤ M ≤ 1000)美元。
然而，他们的问题如此复杂，必须聘请顾问来解决。顾问不是免费的，但他们有能力：顾问可以在一个月内解决任何问题。每位顾问要求两次付款：一次预付（1≤ 付款≤ M） 在月初支付问题解决开始，在问题解决后的月初再支付一次（1≤ 付款≤ M） 。因此，奶牛每个月都可以用上个月赚来的钱来支付顾问费用。牛是挥霍无度的：他们从不每月储蓄一分钱；没用的钱都浪费在买牛奶糖上了。
由于要解决的问题相互依赖，因此必须按顺序解决它们。例如，问题3必须在问题4之前或与问题4在同一个月内解决。
确定解决奶牛所有问题所需的月数，并支付解决方案的费用。

输入格式：

第1行：两个空格分隔的整数：M和P。
第2..P+1行：第i+1行用两个空格分隔的整数描述问题i：Bi和Ai。Bi是在问题解决之前向咨询公司支付的费用；Ai是问题解决后向咨询公司支付的费用。

输出格式：

第1行：解决和支付所有奶牛问题所需的月数。

输入样例#1：

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

输出样例#1：

6

说明：