## Riolku's Mock CCC S4 - Clumsy Cindy

View as PDF

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 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 units into bucket , but unfortunately, in her clumsiness, 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 . 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?

#### Input Specification

The first line will contain , the number of buckets.

The next line will contain integers, the values of .

The next lines will contain and . Note that 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 and is discarded.

It can be shown that it is impossible to fill the buckets in 3 moves or less.