[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 C _{i} and the i-th village can be served by any post office within R_{i} 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 P _{i} money. Here C_{i}, R_{i} and P_{i} 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 C _{1}, C_{2}, ... , C_{N}, each of which is between 0 and 10,000, inclusive.The fourth line of each test case contains N integers R _{1},...,R_{N}, each of which is between 0 and 1,000,000,000, inclusive.The last line of each test case contains N integers P _{1}, ... , P_{N}, 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 |

University of Science and Technology of China

Online Judge for ACM/ICPC

Processed in 1.4ms with 1 query(s).

Online Judge for ACM/ICPC

Processed in 1.4ms with 1 query(s).