Network Flow—Homework Problem #3—Armand's Spoon and Bowl Feeding Machine

Problem: flow3

In case Armand should suffer grave injuries from all the dangerous sports he's been doing, he has built an automatic lunch feeding machine for himself. The lunch feeding machine is built with spoons and bowls. His initial idea was to build a robot with two arms and transfer the food from the fridge to his bed, but that's too slow! Luckily for him, robotic arms are cheap, so he linked all the spoons to robotic arms and put bowls in the intersecting regions between the arms to transfer food from the fridge assembly-line-style. W00t! Oh wait—he forgot to calculate how much food this assembly line can transfer in one shot. Assuming the fridge has an infinite amount of food and can pop the food out into nearby bowls instantly, Armand is infinitely hungry, each spoon and bowl can hold only a finite amount of food, and all food is carried in integer "food units", how many food units can the feeding machine transfer per unit time?

Input

There will be multiple test cases. The last test case will end at the end of the file.

The input will start with a positive integer N indicating the number of bowls (numbered 1 through N). The next few lines contain a total of N positive integers indicating how much food can be stored in each bowl at any given time.

The next line contains another positive integer M, which is the number of spoons in the machine. Following this are M lines each having three positive integers i, j, and C, meaning that this spoon can pick up to C food units up out of bowl i and drop them into bowl j per unit time.

Finally, the next line contains positive integers B and D. B is the number of bowls that are close enough to the fridge that it can add food directly to them, while D is the number of bowls close enough to Armand that he can eat out of them. The next line will contain B+D integers, each of which is a bowl number. The first B indicate which bowls are close to the fridge, while the remaining D indicate which bowls are close to Armand. No bowl will be close to both Armand and the fridge.

Bounds

For each test case, 2 ≤ N ≤ 100 and 1 ≤ (B,D) < N.

Output

For each test case, output a single integer on its own line, indicating the maximum amount of food Armand can be fed per unit time.

Sample Input

4
10 20 30 40
6
1 2 5
1 3 10
1 4 13
2 3 5
2 4 7
3 4 20
3 1
1 2 3 4
2
50 100
1
1 2 100
1 1
1 2

Sample Output

37
50