Problem Description

In a magic world, a warrior needs to pass through a dangerous maze. The maze has $n$ rooms in a line, numbered from $1$ to $n$ from left to right. The warrior must start from room $1$ and go through rooms in order, and only succeeds after leaving room $n$. Each room contains magic shields and magic attacks.

Magic shields can be accumulated, but there is a maximum capacity limit. Room $i$ has $s_i$ magic shields (possibly negative, meaning the shield is consumed), and the maximum accumulated shield capacity is $c$.

At the same time, each room may have a magic attack. Let $a_i$ be the attack power of room $i$. If the shields accumulated by the warrior in a room are less than the attack power, the warrior fails to pass.

Key rules:

• Initially, the warrior has $b$ shields.
• When entering room $i$, the warrior first gains $s_i$ shields ($s_i < 0$ means losing $|s_i|$ shields), and then faces the attack $a_i$.
• Shields have an upper limit. The accumulated shields cannot exceed $c$. If after gaining shields the number of shields is greater than $c$, it immediately becomes $c$.
• If in any room the number of shields is less than the attack power, the adventure fails.
• You may optionally choose some rooms to apply a “shield amplification” effect. In a chosen room, the effect of $s_i$ is doubled. This effect does not affect $a_i$.

Compute the minimum number of rooms that need to use shield amplification for the warrior to successfully pass all rooms. If it is impossible to pass the maze no matter what, output the integer $-1$.

Input Format

The first line contains three integers $n, c, b$, separated by a single space, representing the number of rooms, the maximum shield capacity, and the initial shields.

The second line contains $n$ integers $s_1, s_2, \dots, s_n$, separated by a single space, where $s_i$ represents the shield change in room $i$.

The third line contains $n$ integers $a_1, a_2, \dots, a_n$, separated by a single space, where $a_i$ represents the attack power in room $i$.

Output Format

Output one line containing one integer, the answer, i.e., the minimum number of rooms that need shield amplification to successfully pass the maze. If it is impossible to pass, output the integer $-1$.

5 9 2
6 -3 6 -1 -4
9 6 6 7 4

1

9 9 0
5 3 9 5 -3 7 -1 3 -5
3 4 3 4 2 8 5 1 3

0

Hint

Sample Explanation 1

Apply shield amplification to the first room.

Upon reaching room $1$, the current shields are $\min(2 + 6 \times 2, 9) = 9 \ge 9$, so the warrior can pass room $1$.

Upon reaching room $2$, the current shields are $9 - 3 = 6 \ge 6$, so the warrior can pass room $2$.

Upon reaching room $3$, the current shields are $\min(6 + 6, 9) = 9 \ge 6$, so the warrior can pass room $3$.

Upon reaching room $4$, the current shields are $9 - 1 = 8 \ge 7$, so the warrior can pass room $4$.

Upon reaching room $5$, the current shields are $8 - 4 = 4 \ge 4$, so the warrior can pass room $5$. Therefore, the answer is $1$.

Sample Explanation 2

There is no need to use shield amplification, and the warrior can pass all rooms.

Constraints and Notes for Testdata

For $25\%$ of the testdata, $1 \le n \le 10$.

For $50\%$ of the testdata, $1 \le n \le 20$.

For $60\%$ of the testdata, $1 \le n \le 50$.

For $70\%$ of the testdata, $1 \le n \le 100$.

For $80\%$ of the testdata, $1 \le n \le 1000$.

For all testdata, $1 \le n \le 10000$, $-10000 \le s_i \le 10000$, $1 \le a_i \le 10000$, $1 \le c \le 50000$, $0 \le b \le 50000$.

Translated by ChatGPT 5