F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist

C/C++/Java Exams
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
DIY | Web-DIY beta
Register new ID

# Candy Factory

Time 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 pku-town. 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(si,ti) , meaning that candy i must start producing at time si and will finish at ti. Otherwise if the start time is pi(si < pi < ti) then candy will still finish at ti but need additional K*(pi - si) cost. The candy can’t be produced if pi is greater than or equal to ti. 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 Cij and cost is Dij. To change a machine from the state suitable for candy i1 into the state suitable for candy i2, time required is Ei1i2 and cost is Fi1i2.
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 si and ti(0 <= si < ti <100000).
Then N lines follow, each line contains M integers, the j-th integer of the i-th line indicating Cij(1<=Cij<=100000) .
Then N lines follow, each line contains M integers, the j-th integer of the i-th line indicating Dij(1<=Dij<=100000) .
Then N lines follow, each line contains N integers, the i2-th integer of the i1-th line indicating Ei1i2(1<=Ei1j2<=100000) .
Then N lines follow, each line contains N integers, the i2-th integer of the i1-th line indicating Fi1i2(1 <= Fi1j2<=100000) .
Since the same candy will only be produced once, Eii and Fii 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
3 2 1
4 7
2 4
8 9
4 4
3 3
3 3
2 8
12 3
14 6
-1 1 1
1 -1 1
1 1 -1
-1 5 5
5 -1 5
5 5 -1

1 1 2
1 5
5
5
-1
-1

0 0 0


Sample Output
11
-1

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

Statistic | Submit | Discuss | Note
 Home | Top Hangzhou Dianzi University Online Judge 3.0 Copyright © 2005-2024 HDU ACM Team. All Rights Reserved. Designer & Developer : Wang Rongtao LinLe GaoJie GanLu Total 0.000000(s) query 1, Server time : 2024-08-14 19:18:03, Gzip enabled Administration