Cindy is trying to fill up her row of buckets!
Cindy has a row of ~N~ buckets, each initially empty. She wants to fill them to different capacities, depending on the bucket sizes. To accomplish this, she will pour a certain amount into each bucket.
On one move, she pours ~a_i~ units into bucket ~i~, but unfortunately, in her clumsiness, ~b_i~ units get poured into the next bucket in line! If she pours into the last bucket, she clumsily spills onto the grass instead.
Cindy wants to fill each bucket to a certain capacity ~c_i~. If a bucket's water total exceeds the given capacity, the excess will be spilled onto the grass.
Cindy wants to fill her buckets as fast as possible. She can pour into each bucket as many times as she wants. She wonders: what is the minimum number of moves she has to make to fill all her buckets?
~1 \le N \le 5\,000~
~1 \le a_i, b_i, c_i \le 5\,000~
Subtask 1 [2/15]
~1 \le N \le 10~
~1 \le a_i, b_i, c_i \le 2~
Subtask 2 [5/15]
~1 \le N \le 700~
~1 \le a_i, b_i, c_i \le 700~
Subtask 3 [8/15]
No additional constraints.
The first line will contain ~N~, the number of buckets.
The next line will contain ~N~ integers, the values of ~c_i~.
The next ~N~ lines will contain ~a_i~ and ~b_i~. Note that ~b_N~ indicates the amount of water spilled onto the grass, and can be ignored.
Output the minimum number of times Cindy has to pour to fill all the buckets.
4 6 9 3 8 6 5 4 3 1 5 3 10
Explanation for Sample Output
After pouring once into the first bucket, the amount of water in each bucket is:
6 5 0 0
After pouring once into the second bucket:
6 9 3 0
After pouring twice into the second-last bucket:
6 9 3 8
Note that overflow in buckets ~3~ and ~4~ is discarded.
It can be shown that it is impossible to fill the buckets in 3 moves or less.