你想从你的地产上移除一棵大树，但它太大了，你无法一次性搬走。如果你的最大负重是 $W$，你需要把它切成多少块？

这棵树有一个连接到地面的主干，并可以分叉成多个分支。所有这些分支还可以进一步分叉，以此类推。因此，树的每个片段都是一段连续的木材，它可能分叉成多个分支，也可能不分叉。

你可以在树的任何位置进行切割：起点、终点或任何片段的中间。你可以将分叉视为树的一个极小部分，即你可以在分支分叉之前或之后立即切割，而不会增加基部树枝的重量，但这会影响子分支是被切成一个整体，还是被单独切掉。

输入格式

输入的第一行包含 $W$，即你的最大负重。下一行开始描述第一个树片段（即树干）。

树片段的描述是递归定义的。第一行包含两个数字 $M$（片段的重量）和 $N$（在该片段末端分出的分支数量）。随后是 $N$ 个树片段的描述，分别描述每一个分支。

数据范围

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

输出格式

输出一个数字，即你需要将树切成的块数。

样例

输入 1

1
10 0

输出 1

10

输入 2

7
5 2
7 0
2 0

输出 2

2

输入 3

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

输出 3

5

说明

图片展示了样例测试用例的一些可能解法。