Deep Sea Adventure 1
Submit solution
All submissions
Best submissions
Points:65 (partial)
Time limit:1.0s
Memory limit:128M
Author:
admin
Problem type
Allowed languages
C
Problem Statement
Percy begins his dive at the surface with a limited amount of oxygen supply. There are several underwater stations situated at various depths, each containing air tanks to refill your oxygen supply. However, it takes time to refill oxygen. The objective is to reach the underwater cave without running out of oxygen and minimizing the time that is spent at the stations.

Percy starts a depth of 
 and has an initial oxygen supply of 
 amount. Every unit depth that he descends, he consumes 
 unit of oxygen supply. The final depth that he needs to reach is 
.

To help refill oxygen, there are 
 stations present at various depths. Each station fills Percy's oxygen tank with exactly 
 units of oxygen. There is no way to only partially refill. The 
th station is present at a depth 
i and takes 
i time to refill the 
 units of oxygen. You can refill oxygen from a station only once, that too only if you have reached its depth. Also, no two stations are present at the same depth.

You have to help Percy figure out if it is possible for him to reach the underwater cave without running out of oxygen and the minimum total time that he has to spend refilling in order to do so.

Input Format
The first line of input contains integers 
, 
, 
 and 
 denoting the number of stations, initial oxygen supply, the final depth and the amount of oxygen refilled at each station respectively.

The second line contains 
 integers representing the depths 
i of each station from the top.

The third line contains 
 integers representing the refilling times 
i of each station.

Constraints


i 

i 

All 
i are distinct

Output Format
If it is possible for Percy to reach the depth 
, print the minimum total time that he has to spend at the stations.

If it is not possible for him to reach depth 
, print 
 followed by the maximum depth that he can reach before his oxygen level goes to 
.

Sample Test Case 1:
Input:
Copy
3 10 20 6
7 2 14
3 8 4
Output:
Copy
7
Explanation:
Percy has to reach a depth of 
. He cannot reach it with the initial oxygen supply he has. Therefore, he refills oxygen at the stations located at depths 
 and 
, gaining 
 units of oxygen at each station, with a minimal total refilling time of 
 to be able to reach the depth of 
.

Sample Test Case 2:
Input:
Copy
2 7 15 4
7 11
3 5
Output:
Copy
8
Explanation:
Percy has to reach a depth of 
. He cannot reach it with the initial oxygen supply he has. Therefore, he refills oxygen at the stations located at depths 
 and 
, gaining 
 units of oxygen at each station, with a minimal total refilling time of 
 to be able to reach the depth of 
.

Sample Test Case 3:
Input:
Copy
4 12 22 3
18 8 19 16
1 2 3 4
Output:
Copy
-1 15
Explanation:
Percy has to reach a depth of 
. He cannot reach it with the initial oxygen supply he has. He refills oxygen at the station located at depth 
 and is able to reach a depth of 
. But he runs out of oxygen at this point and cannot go any further.

do this using heaps. give code in c and explain the logic too