Deforestation

Interview

Time limit2sMemory limit1024 MB

Summary

Given a tree of segment weights and a carrying limit W, find the minimum number of pieces needed so that each piece weighs at most W.

Level: Medium5 of 10
Topics: Greedy, Tree, Sorting
Solved: No attempts yet

Problem

You want to remove a big tree from your property, but it is too big to carry all at once. If the maximum weight you can carry is $W$ , how many pieces do you have to cut it into?

The tree has a single trunk connected to the ground, and the trunk can split into multiple branches. Each branch can branch out further, and so on. Each segment of the tree is a continuous mass of wood, which may or may not split into multiple branches.

You can make cuts at any point on the tree: at the start, at the end, or anywhere in the middle of any segment. Branching is treated as an arbitrarily small part of the tree. You can cut immediately before or after a branch splits off without increasing the weight of the base branch, but this choice decides whether the child branches are cut off as a single piece or whether only one branch is cut off separately.

Input

The first line contains $W$ , your carrying capacity. The next line describes the first tree segment, its trunk.

A tree segment is described recursively. The first line contains two numbers: $M$ , the weight of the segment, and $N$ , the number of branches coming out of the segment at its end. The $N$ tree segment descriptions follow, one for each branch.

Output

Print one number, the number of pieces you have to cut the tree into.

Constraints

$1 \leq W, M \leq 10^9$
$0 \leq N \leq 10^5$
The total weight of all tree segments does not exceed $10^9$ .
The total number of segments does not exceed $10^5$ .

Hints

The image shows some possible solutions for the sample test cases.

Examples3

Example 1
Input
```
1
10 0
```
Expected output
```
10
```
Example 2
Input
```
7
5 2
7 0
2 0
```
Expected output
```
2
```
Example 3
Input
```
5
2 3
2 2
1 0
1 0
6 0
4 2
3 0
2 0
```
Expected output
```
5
```