Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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.


  • 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

    Sample Output 1

  • Sample Input 2

    1 1 0

    Sample Output 2