Road to a New Life#11306
Having successfully passed his exams, Petryk is going to drive to his parents in Kremenchuk, which is kilometers away from the university.
Petryk's car is not new, so it consumes as much as liters of gasoline per kilometer. Along the way to his home, there are gas stations, each offering fuel at c_i hryvnias per liter and located at a distance of x_i kilometers from the starting point. However, surprisingly, each gas station offers its own unique type of gasoline, which cannot be mixed in the tank.
Before the trip, Petryk wants to replace the fuel tank, but he doesn't know which size to choose. Help Petryk determine the minimum fuel tank size such that the cost of the trip to his relatives will be minimal. That is, the priority is to minimize fuel expenses.
It is guaranteed that the tank is initially empty and there exists such that x_i = 0.
The first line contains two integers (1 \le d, w \le 10^6).
The second line contains one integer (1 \le n \le 10^3).
The third line contains integers c_i (0 \le c_i \le 10^6).
The fourth line contains integers x_i (0 \le x_i \le d).
It is guaranteed that there exists such that x_i = 0.
Print the minimum fuel tank size such that the cost of the trip will be minimal.
Example 1
Example 2
In the first example, the road length is kilometers, and fuel consumption is liters per kilometer. There are only two gas stations: one at the starting point with a price of hryvnias per liter, and one at a distance of kilometers with a price of hryvnia per liter. Since the second gas station has the cheapest price, it is optimal to refuel minimally at the first station to reach the second one. Then at the first gas station, one should refuel 4 \cdot 10 = 40 liters of gasoline, and at the second one refuel the necessary 6 \cdot 10 = 60 liters of gasoline to cover the rest of the journey. Thus, the minimum tank size for such a trip to be possible is liters.
In the second example, the road length is kilometers, and fuel consumption is liters per kilometer. There are only two gas stations: one at the starting point with a price of hryvnias per liter, and one at a distance of kilometers with a price of hryvnias per liter. Since the first gas station has the cheapest price, it is optimal to refuel there for the entire journey. Then at the first gas station, one should refuel 5 \cdot 10 = 50 liters of gasoline, and not refuel at the second one. Thus, the minimum tank size for such a trip to be possible is liters.
This problem uses per-test scoring. If your solution works correctly under the following constraints, it is guaranteed to receive at least this many points:
1. ( points): n \leq 16; 2. ( points): c_1 = c_2 = \dots = c_n; 3. ( points): w=1; d \leq 10^3; 4. ( points): without additional constraints.