|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2 초||256 MB||13||11||10||90.909%|
There is a long-distance coach between the city I and the city O. It has a water supply machine. Passengers and the driver can drink water from it. The coach departs from the city I at time 0, and arrives the city O at time X. On the route, there are N refilling points where we can put water into the machine. The coach will arrive at the i-th refilling point (1 ≤ i ≤ N) at time Si.
In the beginning, the machine does not have water in it. We can put water into it before departure. Also, we can put water into it when the coach is at a refilling point. The cost of water is W yen per liter regardless of the position of the coach.
At the city I, M passengers get on the coach. The passengers are numbered from 1 to M. No passengers get on the coach at places other than the city I. The j-th passenger (1 ≤ j ≤ M) needs a liter of water at time Dj. If he drinks water, he will need a liter of water after a lapse of time T. In other words, the j-th passenger needs water at time Dj + kT (k = 0, 1, 2, . . .). Here, 1 ≤ Dj < T is satisfied, and the value of T is the same for all passengers. If the machine does not have water in it when a passenger needs water, the passenger leaves the coach. If the j-th passenger leaves the coach before getting to the city O, we need to refund the fare. The cost for refund is Cj yen.
The driver also needs water. If he drinks water, he will need a liter of water after a lapse of time T, just in the same way as passengers. In other words, the driver needs water at time kT (k = 0, 1, 2, . . .). If the machine does not have water in it when the driver needs water, the operation of the coach is stopped.
No two people will need water at the same time. When the coach arrives at the city O or a refilling point, neither passengers nor the driver need water.
Adjusting the amount of water put into machine at refilling points, we want to minimize the sum of the cost of water and the cost of refund, and to operate the coach until the city O. Your task is to decide where and how much we should put water into the water supply machine during the travel.
Given the traveling time for the coach, information on refilling points, and information on passengers and the driver, write a program which calculates the minimum of the sum of the cost of water and the cost of refund assuming the coach gets to the city O.
Read the following data from the standard input.
Write one line to the standard output. The output contains an integer, the minimum total cost.
N ≤ 8, M ≤ 8.
N ≤ 100, M ≤ 100.
N ≤ 2 000, M ≤ 2 000.
There are no additional constraints.
19 1 4 8 7 10 1 20 2 10 4 5 6 5
In this sample input, if we put 7 liters of water into the machine before departure, and 4 liters of water into the machine at the first refilling point, the coach will be operated as follows:
Total amount of water used is 11 liters. The cost of water is 88 yen. The sum of the cost of refund for the passengers 2, 3 is 15 yen. The total sum is 103 yen.
We output 103 because it is impossible to operate the coach if the total cost is less than or equal to 102 yen,
105 3 5 9 10 59 68 71 4 71 6 32 7 29 3 62 2 35
1000000000000 1 1 1000000 6 999999259244 1 123456789