Golden Transport Trade Optimization

Golden Transport Trade Optimization

After being discharged from the hospital, mzry1992 bought a new motorcycle and started a lucrative gold transportation business among nearby cities. The cities are connected by bidirectional highways, each with a weight (cargo) limit. If mzry1992 carries gold exceeding the limit of a highway, his motorcycle cannot use that highway.

This year, mzry1992 received n orders from n different cities. Each order is one of two types:

• A sell order: The customer offers to sell gold (mzry1992 buys gold), with an upper limit on the amount.
• A buy order: The customer wants to buy gold from mzry1992, with an upper limit on the amount.

The orders must be processed in the order they are received. When processing the i^th order, mzry1992 must:

1. Travel from his current city to the city where the i^th customer resides. He may pass through other cities. If he travels by highway, his load of gold must not exceed the highway limits along his chosen route. However, there is a free train system available: if both the departure and arrival cities have train stations, he can take the train carrying any amount of gold (no weight limit) along with his motorcycle.
2. Perform the transaction with the customer. In doing so he wishes to maximize the transaction amount subject to the following restrictions:
   • After completing the final order, he must have no gold in hand.
   • At no time should he pick up more gold than he can safely carry on the subsequent journey (so that he never has to discard gold due to transport limits).

Initially, mzry1992 is located at the city of the first order. Under an optimal (maximum‐trade) strategy, determine the purchase amounts for each customer who places a buy order (i.e. the customers buying gold from mzry1992).

Input/Output details: See below.

inputFormat

The input is given as follows:

 n m k
 c1 c2 ... cn
 t1 t2 ... tn
 l1 l2 ... ln
 (next m lines): u v w
 (last line): s1 s2 ... sk

Here:

• n is the number of orders.
• m is the number of highways.
• k is the number of cities that have a train station.
• The second line gives n integers, where the i^th integer is the city where the i^th order is located. (Cities are numbered starting from 1.)
• The third line gives n integers representing the order types. A value of 0 indicates a sell order (the customer sells gold to mzry1992) and a value of 1 indicates a buy order (the customer buys gold from mzry1992).
• The fourth line gives n integers, where the i^th integer is the upper limit for the transaction amount in the i^th order.
• Each of the next m lines contains three integers u v w, indicating a bidirectional highway between city u and city v with a weight limit of w.
• The last line contains k integers, the list of cities which have a train station. (If k is 0, the line will be empty.)

Note on travel: When traveling from city A to city B, if both cities have a train station, mzry1992 may use the train and ignore highway limits (effectively, the capacity is infinite). Otherwise, he must travel via highways and the maximum load he can carry is equal to the maximum bottleneck capacity between A and B (i.e. the maximum over all paths of the minimum highway limit along that path). You may assume that the highway network is connected.

outputFormat

Output a single line containing the purchase amounts for each buy order (i.e. for each order with type 1) in the order they appear in the input, separated by a space.

sample

4 3 4
1 2 3 4
0 1 0 1
100 50 50 70
1 2 100
2 3 100
3 4 100
1 2 3 4

50 70