There is a straight highway with N villages alongside it. The villages are
numbered from 1 to N in one direction of the highway.The government is planning to
build at most M post offices in some of the villages.
The amount of money to build a post office in the i-th village is Ci and the i-th
village can be served by any post office within Ri kilometers to the left or right of it.
If a village has no post office built and no post offices in other villages can serve it,
the government has to compensate the villagers Pi money. Here Ci, Ri and Pi are all
non-negative integers.
You are to help the government to find a strategy of minimum cost.
The input consists of multiple test cases. Each test case starts with a line containing
two integers N(2<=N<=20,000) and M (1<=M<=N, M<=100).
The following line contains N-1 positive integers, which are the distances of between
village 1 and villages 2 ,3,...,N in kilometers.
The distances will be not greater than 1,000,000,000 and strictly increasing.
The third line of each test case contains N integers C1, C2, ... , CN, each of which is
between 0 and 10000, inclusive.
The fourth line of each test case contains N integers R1,...,RN, each of which is
between 0 and 1000000000, inclusive.
The last line of each test case contains N integers P1, ... , PN, each of which is between
0 and 10000, inclusive.
The last test case is followed by a line containing two zeros.
For each test case, print a line containing the test case number ( beginning with 1)
followed by the minimum amount of money the government has to pay.
3 2 1 2 2 3 2 1 1 0 10 20 30 3 2 10 20 100 2 300 5 6 7 10 100 400 0 0
Case 1: 4 Case 2: 312
Migrated from old NTUJ.
2009Hefei
| No. | Testdata Range | Score |
|---|