Training Site

# Roller Coaster Magnate

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 1.0 seconds

Congratulations! As the proud new owner of a S.T.E.V.E. Corporation Super Roller Coaster 2000$^{TM}$, you have decided to open your and exciting theme park, C World$^{TM}$.

At the center of your attraction is a roller coaster track made up of $N$ meter-long sections. A ride starts at the first section with an arbitrary non-negative speed, which you can control. Each following section is either an up section or a down section, which will decrease or increase the speed of the ride by $s$ m/s. The speed of a ride will change instantaneously once it enters each section, and you cannot control the speed of a ride other than its initial speed. If the speed of a ride reaches $0$ m/s then it will stop immediately and not continue onto further sections. The ride's brake system will stop it if it reaches the end of the last section, or attains a negative speed. Additionally, you have control of the brake system so you can decide to terminate the ride at any particular point.

There are $M$ people in your ride. Unfortunately, because you've been cutting costs on food security by selling dubiously hygienic watermelons, some passengers may have rather unstable stomachs due to mild food poisoning. The $i$-th person to get onto the ride is able to withstand a maximum speed of $x_i$ m/s before they throw up. You have enough money left in your budget to bribe $K$ people so that they will not leave negative reviews on the review website Kelp$^{TM}$. Therefore, you are not allowed to have more than $K$ people throw up, otherwise you will have to shut down your park due to negative publicity / health and safety violations.

Your task is to find the maximum distance (in meters) your ride can travel with at most $K$ people throwing up. As you can simply terminate the ride after this maximum distance, it does not matter if people would throw up past this point.

## Input Format

The first line of input will contain the three space-separated integers $N$, $M$ and $K$.

Following will be $N$ lines. The $i$-th such line will contain an integer $s_i$, where $s_i$ is the change in speed of the $i$-th section. Thus, for an up section $s_i \le 0$, and for a down section $s_i \ge 0$.

Finally will be $M$ lines. The $i$-th such line will contain an integer $x_i$, where $x_i$ is the maximum speed the $i$-th person can withstand without throwing up.

## Output Format

Output a single integer $A (A \le N)$, where $A$ is the maximum distance (in meters) your ride can travel with at most $K$ people throwing up.

## Constraints

• $1 \le N \le 100,000$
• $1 \le M \le 100,000$
• $0 \le K \le M$
• $-1000 \le s_i \le 1000$
• $0 \le x_i \le 1,000,000,000$

• Subtask 1 (20%): $s_i>0$ for all $i$ - that is, all sections are down sections
• Subtask 2 (20%): $N, M \le 1000$
• Subtask 3 (60%): No further constraints apply

## Explanation of Sample Cases

### Sample Input 1:

One optimal solution is to start the ride off with a speed of 2 m/s. Thus in the first section the ride has a speed of 4 m/s, increasing to 8 m/s in the next section. At this point, the first two passengers throw up as they can only stand speeds of 4 and 5 m/s respectively. In the third section the speed decreases to 2 m/s then increases to 10 m/s in the fourth section. The ride stops in the fifth section as its speed becomes negative (-2 m/s). Thus the maximum distance is 4 meters, as only two passengers have thrown up at this point.

### Sample Input 2:

There is a single down section and a single passenger, who is not allowed to throw up. One solution would be to start the ride with a speed of 0 m/s, so that it passes the first section with a speed of 5 m/s before reaching the end of the ride and stopping. Thus the maximum distance is 1 meter.

• ### Sample Input 1

5 5 2
2
4
-6
8
-12
4
5
10
11
14


### Sample Output 1

4

• ### Sample Input 2

1 1 0
5
5


### Sample Output 2

1