Road to a new life.#7

Road to a new life.

1 second
256 megabytes
Hard

After a successful session, Petryk plans to visit his parents in Kremenchuk by car. The distance from the university to Kremenchuk is kilometers. Petryk's car is not new, so it consumes liters of gasoline per kilometer. There are 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 such that x_i=0.

The first line contains two integers (1\leq d,w \leq 10^6).

The second line contains one integer (1\leq n\leq 10^3).

The third line contains integers c_i (0\leq c_i \leq 10^6).

The fourth line contains integers x_i (0\leq x_i \leq d).

It is guaranteed that there is an 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 kilometers and the gasoline consumption is liters per kilometer. There are only two gas stations: the initial station with a price of hryvnias per liter and another one kilometers away with a price of 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, 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 liters.

In the second example, the length of the road is kilometers and the gasoline consumption is liters per kilometer. There are only two gas stations: the initial station with a price of hryvnias per liter and another one kilometers away with a price of 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, 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 liters.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading