Riolku's Mock CCC S4 - Clumsy Cindy

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem type

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?

Constraints

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.

Input Specification

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 Specification

Output the minimum number of times Cindy has to pour to fill all the buckets.

Sample Input

4
6 9 3 8
6 5
4 3
1 5
3 10

Sample Output

4

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.


Comments

There are no comments at the moment.