You want to remove a big tree from your property, but it's too big for you to carry all at once. How many pieces do you have to cut it into if the maximum weight you can carry is $$$W$$$?
The tree has a single trunk connected to the ground and can split out into multiple branches. All of those branches can branch out further etc. So each segment of the tree is a continuous mass of wood, which may or may not split out into multiple branches.
You can make cuts at any point on the tree; start, end, or anywhere in the middle of any segment. You can consider branching as an arbitrarily small part of the tree, i.e. you can cut immediately before or after a branch splits off without increasing the weight of the base branch, but it will affect whether the child branches are cut off as a single piece or just one branch is cut off separately.
The first line of the input will contain $$$W$$$, your carrying capacity. The next line will continue with the description of the first tree segment; its trunk.
A tree segment description is defined recursively. The first line contains two numbers $$$M$$$, weight of the segment, and $$$N$$$, number of branches coming out of the segment at its end. This is followed by $$$N$$$ tree segment descriptions, describing each one of the branches.
Input limits
- $$$1 \leq W, M \leq 10^9$$$
- $$$0 \leq N \leq 10^5$$$
- Total weight of all tree segments will not exceed $$$10^9$$$.
- Total number of segments will not exceed $$$10^5$$$.
Output one number, the number of pieces you have to cut the tree into.
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
Image shows some possible solutions of sample test cases.
