

Candy FactoryTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 662 Accepted Submission(s): 342 Problem Description A new candy factory opens in pkutown. The factory import M machines to produce high quality candies. These machines are numbered from 1 to M. There are N candies need to be produced. These candies are also numbered from 1 to N. For each candy i , it can be produced in any machine j. It also has a producing time(s_{i},t_{i}) , meaning that candy i must start producing at time s_{i} and will finish at t_{i}. Otherwise if the start time is p_{i}(s_{i} < p_{i} < t_{i}) then candy will still finish at t_{i} but need additional K*(p_{i}  s_{i}) cost. The candy can’t be produced if p_{i} is greater than or equal to t_{i}. Of course one machine can only produce at most one candy at a time and can’t stop once start producing. On the other hand, at time 0 all the machines are in their initial state and need to be “set up” or changed before starting producing. To set up Machine j from its initial state to the state which is suitable for producing candiy i, the time required is C_{ij} and cost is D_{ij}. To change a machine from the state suitable for candy i_{1} into the state suitable for candy i_{2}, time required is E_{i1i2} and cost is F_{i1i2}. As the manager of the factory you have to make a plan to produce all the N candies. While the sum of producing cost should be minimized. Input There are multiple test cases. For each case, the first line contains three integers N(1<=N<=100), M(1<=M<=100), K(1<=K<=100) . The meaning is described above. Then N lines follow, each line contains 2 integers s_{i} and t_{i}(0 <= s_{i} < t_{i} <100000). Then N lines follow, each line contains M integers, the jth integer of the ith line indicating C_{ij}(1<=C_{ij}<=100000) . Then N lines follow, each line contains M integers, the jth integer of the ith line indicating D_{ij}(1<=D_{ij}<=100000) . Then N lines follow, each line contains N integers, the i_{2}th integer of the i_{1}th line indicating E_{i1i2}(1<=E_{i1j2}<=100000) . Then N lines follow, each line contains N integers, the i_{2}th integer of the i_{1}th line indicating F_{i1i2}(1 <= F_{i1j2}<=100000) . Since the same candy will only be produced once, E_{ii} and F_{ii} are meaningless and will always be 1. The input ends by N=0 M=0 K=0. Cases are separated with a blank line. Output For each test case, if all of M candies can be produced, output the sum of minimum producing cost in a single line. Otherwise output 1. Sample Input
Sample Output
Hint For the first example, the answer can be achieved in the following way: In the picture, S i represents setting up time for candy i, A i represents changing time for candy i and P i represents producing time for candy i . So the total cost includes: setting up machine 1 for candy 1, costs 2 setting up machine 2 for candy 2, costs 3 changing state from candy 2 to candy 3, costs 5 late start of candy 2, costs 1 Source  
