| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1132
Post offices
Time Limit: 6000ms
Memory Limit: 65536kb Description
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. Input
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 10,000, inclusive. The fourth line of each test case contains N integers R1,...,RN, each of which is between 0 and 1,000,000,000, inclusive. The last line of each test case contains N integers P1, ... , PN, each of which is between 0 and 10,000, inclusive. The last test case is followed by a line containing two zeros. Output
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.
Sample Input
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 Sample Output
Case 1: 4 Case 2: 312 |