Description

你想要从你的土地上移除一棵大树，但它太大了，你无法一次性搬走。若你一次最多能搬运 $W$ 重量，你需要把这棵树切成多少段才能搬走？

这棵树有一根主干与地面相连，并且可以分出多根分支。所有这些分支还可以继续分叉，依此类推。因此，树的每一段都是一段连续的木头，可能会分出多个分支，也可能没有。

你可以在树的任意位置切割：起点、终点或任何一段的中间。你可以把分叉点看作树上的一个极小的部分，也就是说，你可以在分叉前后立即切割，而不会增加主干的重量，但这会影响子分支是作为一个整体被切下，还是只切下其中一根分支。

Input Format

输入的第一行包含一个整数 $W$，表示你一次能搬运的最大重量。下一行开始描述树的第一段，也就是主干。

一段树的描述是递归定义的。第一行包含两个整数 $M$（该段的重量）和 $N$（该段末端分出的分支数）。接下来是 $N$ 段树的描述，分别描述每一根分支。

Output Format

输出一个整数，表示你需要把树切成多少段才能搬走。

1
10 0

10

7
5 2
7 0
2 0

2

5
2 3
2 2
1 0
1 0
6 0
4 2
3 0
2 0

5

Hint

说明

下图展示了样例测试用例的一些可能的切割方案。

:::align{center} :::

输入范围

• $1 \leq W, M \leq 10^9$
• $0 \leq N \leq 10^5$
• 所有树段的总重量不超过 $10^9$。
• 树段总数不超过 $10^5$。

由 ChatGPT 4.1 翻译