P2876 [USACO07JAN] Problem Solving G

题目描述

在较为轻松的日子里，Farmer John 的奶牛们没有任何问题。然而，如今它们却有许多问题，确切地说，它们有 $P$ 个问题，其中 $1 \leq P \leq 300$。它们已经停止提供牛奶，并像其他好公民一样找了常规工作。实际上，在一个正常的月份里，它们可以赚取 $M$ 的钱，其中 $1 \leq M \leq 1000$。

然而，它们的问题非常复杂，以至于必须雇佣顾问来解决。顾问不是免费的，但他们很有能力：顾问可以在一个月内解决任何一个问题。每个顾问要求两次付款：一次是在开始解决问题的月份开始时支付的预付款（$1 \leq \text{payment} \leq M$），另一次是在问题解决后的下个月开始时支付的尾款（$1 \leq \text{payment} \leq M$）。因此，每个月奶牛们可以用上个月赚的钱来支付顾问的费用。奶牛们是挥霍无度的，它们无法从一个月到下个月存钱；未使用的钱会浪费在牛糖果上。

由于要解决的问题之间存在依赖关系，它们必须大部分按顺序解决。例如，问题 3 必须在问题 4 之前解决，或者与问题 4 在同一个月解决。

确定解决所有奶牛问题并支付解决费用所需的月份数。

输入格式

第 1 行：两个用空格分隔的整数：$M$ 和 $P$。

第 2 行到第 $P+1$ 行：第 $i+1$ 行描述问题 $i$，包含两个用空格分隔的整数：$B_i$ 和 $A_i$。$B_i$ 是在问题解决之前支付给顾问的费用；$A_i$ 是在问题解决之后支付给顾问的费用。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

6

说明/提示