Execution time limit is 1 second

Runtime memory usage limit is 256 megabytes

After a successful session, Petryk plans to visit his parents in Kremenchuk by car. The distance from the university to Kremenchuk is $d$ kilometers. Petryk's car is not new, so it consumes $w$ liters of gasoline per kilometer. There are $n$ gas stations along the way, each offering fuel at a price of $c_{i}$ hryvnias per liter and located at a distance of $x_{i}$ kilometers from the starting point. However, every gas station offers its own unique type of gasoline, which cannot be mixed in the tank. Before the trip, Petryk wants to replace the size of the fuel tank, but does not know exactly which one. Help Petryk determine the minimum size of the fuel tank such that the cost of the trip to his relatives is minimized. In other words, first of all, the cost of fuel should be minimized.

It is guaranteed that at the beginning the fuel tank is empty and that there is an $i$ such that $x_{i}=0$.

The first line contains two integers $d,w$ ($1≤d,w≤10_{6}$).

The second line contains one integer $n$ ($1≤n≤10_{3}$).

The third line contains $n$ integers $c_{i}$ ($0≤c_{i}≤10_{6}$).

The fourth line contains $n$ integers $x_{i}$ ($0≤x_{i}≤d$).

It is guaranteed that there is an $i$ such that $x_{i}=0$.

Output the minimum size of the fuel tank so that the cost of the trip is minimized.

In the first example, the length of the road is $10$ kilometers and the gasoline consumption is $10$ liters per kilometer. There are only two gas stations: the initial station with a price of $2$ hryvnias per liter and another one $4$ kilometers away with a price of $1$ hryvnia per liter. Since the price is cheapest at the second station, it is optimal to refuel minimally at the first station to reach the second. Thus, $40$ liters of gasoline should be filled up at the first station, and the remaining $6∗10=60$ liters of gasoline necessary to complete the journey should be filled up at the second station. Thus, the minimum tank size for this trip is $60$ liters.

In the second example, the length of the road is $10$ kilometers and the gasoline consumption is $5$ liters per kilometer. There are only two gas stations: the initial station with a price of $2$ hryvnias per liter and another one $2$ kilometers away with a price of $4$ hryvnias per liter. Since the price is cheapest at the first station, it is optimal to refuel there until the end of the road. Thus, $50$ liters of gasoline should be filled up at the first station and no refueling is needed at the second station. Thus, the minimum tank size for this trip is $50$ liters.

Input #1

Answer #1

Input #2

Answer #2