LCC '23 Contest 2 J2 - Knives

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

After entering the portal, Macduff is brought to a spooky corridor, with a portal on the other end of the room. Macbeth is standing at the other end of the corridor, laughing:

Is that a dagger I see before me?

Suddenly N daggers appear in a line, filling the corridor. Macbeth enters the portal on the other end of the room.

Macduff needs to chase after Macbeth. He knows that the i^{th} dagger does x_i damage, and that he needs to get through all daggers to reach the portal. He knows that he currently has H health. If his health goes to 0, he will die.

Luckily, Macduff has M health potions, the j^{th} of which will increase his health by h_j. He can only use one potion. Macduff wants to know how many of the health potions he has will allow him to make it to the other end of the room. Can you help?


Subtask 1 [50%]

1 \le N, M \le 10^3

1 \le H, x_i \le 10^3

1 \le h_j \le 10^6

Subtask 2 [50%]

1 \le N, M\le 10^6

1 \le H, x_i \le 10^3

1 \le h_j \le 10^9

Input Specification

The first line will contain integers N, M, and H.

The second line will contain N integers, x_i.

The third and final line will contain M integers, h_j.

Output Specification

Output the number of health potions Macduff has that will allow him to make it to the other end of the room.

Sample Input

5 3 5
1 2 3 4 5
5 10 11

Sample Output


Sample Explanation

Only the third health potion will allow him to go through the knives without reaching a health of less than or equal to 0.


There are no comments at the moment.