Drive

Interview

Time limit1sMemory limit256 MB

Summary

Given D, tank capacity C, consumption E, and stations with distances and prices, find the cheapest way to reach distance D starting with a full tank, or report -1.

Level: Medium7 of 10
Topics: Greedy, Stack, Implementation, Intervals
Solved: No attempts yet

Problem

Giseop got a driver's license and bought a new car so he could travel with his girlfriend. But she dumped him. Feeling down, Giseop decides to go for a drive to clear his head.

The total distance from Giseop's home to his driving destination is D km. The car he bought has a fuel capacity of C liters and a fuel efficiency of E (L/1 km), so he may not be able to reach the destination from home in one go. Fortunately, there are N gas stations between home and the destination, located S1, S2, …, SN (km) away from home. (S1 is the distance between home and the first gas station.) Each gas station may sell fuel at a different price.

Giseop spent a lot of money on the car, so he wants to reach the destination at minimum cost. Find the minimum cost for Giseop to reach the destination. When Giseop leaves home, the tank is full.

Input

The first line gives the vehicle's maximum fuel capacity C, the amount of fuel the vehicle uses to travel 1 km E, and the distance to the destination D.

The second line gives the number of gas stations N. If N=0, no further input is given.

The third line gives the distances between gas stations S1, S2, …, SN, separated by a single space.

The fourth line gives the price per liter of fuel P1, P2, …, PN from the first gas station to the Nth gas station in order, separated by a single space.

Output

Print the minimum fuel cost needed to reach the destination.

If the destination cannot be reached, print -1.

Constraints

1 ≤ D ≤ 10,000, 1 ≤ S1, S2, …, SN ≤ 10,000
1 ≤ C, E ≤ 500, 0 ≤ N ≤ 1,000, 1 ≤ P1, P2, …, PN ≤ 10,000

Examples2

Example 1
Input
```
10 2 10
3
3 4 2
2 3 1
```
Expected output
```
20
```
Example 2
Input
```
20 2 40
4
2 5 3 2
20 10 15 10
```
Expected output
```
-1
```