Server Time: Tue Jul 23, 2019 12:46 am
Welcome ( logout
1361 - Component Placement
  PDF (English) Statistics Forum
Time Limit: 4 second(s) Memory Limit: 32 MB

In circuit design, component placement is an important step in the design automation. Inferior placements may affect the performance and manufacturing cost.

You are given a PCB (Printed Circuit Board). It's a large green board. You can place components on either side of the PCB. However, cost of placing a component on both sides are not the same.

You are given n components. For each component ci, cost of placing it on the top layer is Xi and on the bottom layer is Yi. These components may interact with each other. If both the components are on the same side of the PCB, the interconnection cost is negligible. But, if they are on different sides, their interconnection is costly. For each such interconnection j, the cost will be Zj.

Finally, some design issues restricts some components to be on the top side or bottom side. Now, find the minimum cost to place the components.

Input

Input starts with an integer T (≤ 35), denoting the number of test cases.

Each case starts with a line containing two integers N and M (1 ≤ N ≤ 200, 0 ≤ M ≤ N*(N-1)/2), where N denotes the number of components, M denotes the number of interconnections.

Then there will be two lines, first line contains N integers, where ith of it describes the cost of placing the component on the top layer. The next line contains N integers denoting the costs for placing the components on the bottom layer respectively. These integers will lie in the range [1, 107].

The next line contains N integers ranging in [-1, 1] where -1 denotes the ith component must be placed on bottom, +1 means it must be placed on top and 0 means it can be placed on either side.

Then there will be M lines, each containing three integers p q r (1 ≤ p, q ≤ N, p ≠ q, 1 ≤ r ≤ 107), denoting that, pth and qth component has to be interconnected and if they are on different layers, the cost of interconnection will be r. There will be at most one interconnection between any pair or components.

Output

For each case, print the case number and the minimum cost to place the components.

Sample Input

Output for Sample Input

5

4 0

5 6 7 8

8 7 6 5

0 0 0 0

4 2

5 6 7 8

8 7 6 5

0 0 0 0

1 3 10

2 4 10

4 3

5 6 7 8

8 7 6 5

0 0 0 0

1 3 10

2 4 10

2 3 1

4 3

5 6 7 8

30 31 32 33

0 0 0 0

1 3 10

2 4 10

2 3 1

4 3

5 6 7 8

8 7 6 5

-1 0 0 1

1 2 10

3 4 10

2 3 1

Case 1: 22

Case 2: 24

Case 3: 25

Case 4: 26

Case 5: 31

Note

Dataset is huge, use faster I/O methods.


Problem Setter: Manzurur Rahman Khan
Special Thanks: Jane Alam Jan, Samee Zahur
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan