Packages Par Avion

You operate the airmail system for a delivery company at one airport, called airport 0. The company runs reception desks and a fleet of planes that fly between airports; a separate ground company handles final delivery once a parcel reaches the airport closest to its address. Each day you must decide which parcels to load onto the planes leaving airport 0.

A day proceeds as follows.

• Reception. Customers bring parcels to airport 0. Each parcel has an integer weight in kilograms (already rounded up), a destination airport (the airport nearest its delivery address), a timestamp, and a value in dollars. Parcels arrive in increasing timestamp order and all timestamps are distinct. The reception area holds at most $C$ kg in total: process the day's parcels in timestamp order and accept a parcel only if the running sum of accepted weights stays at most $C$; otherwise reject it. A later, lighter parcel may still be accepted after a heavier one is rejected.
• Loading bay. When reception closes, every accepted parcel joins the parcels already in airport 0's loading bay (parcels left from earlier days, or partway through a multi-hop trip). Each airport reports the total weight of the parcels currently in its own loading bay.
• Choosing a next hop. For every parcel in airport 0's loading bay, consider the routes from airport 0 to the parcel's destination using today's flights, and pick a route with the fewest flights (hops). If several routes are equally short, prefer the one whose first flight goes to the airport with the smallest total loading-bay weight; if that still ties, prefer the smaller airport number. The parcel's next hop is the first airport of the chosen route. If the destination is unreachable, the parcel stays in the loading bay.
• Loading the planes. Each plane leaving airport 0 may carry the parcels whose next hop is that plane's destination, up to the plane's weight capacity in kilograms. Choose a subset of those parcels with the greatest possible total value (a 0/1 knapsack by weight). When several subsets reach that maximum value the reported total is unaffected, so any of them may be loaded; parcels that do not fit wait for another day.

Report, for each flight leaving airport 0, the total value of the parcels loaded onto it.

The input contains several independent loading problems. Each problem begins with a line of five integers $A$ $F$ $P$ $B$ $C$:

• $A$ — the number of other airports, numbered $1$ to $A$ (your own airport is airport $0$);
• $F$ — the number of flights today;
• $P$ — the number of parcels brought in by customers today;
• $B$ — the number of parcels already in the loading bay;
• $C$ — the reception area's weight capacity.

The next $A$ lines each contain one integer: the total loading-bay weight at airports $1, 2, \dots, A$, in that order.

The next $F$ lines each describe a flight as three integers $s$ $d$ $c$ — it flies from airport $s$ to airport $d$ carrying up to $c$ kg. Airport $0$ is your airport, and there is at most one flight for each ordered pair of airports. Flights are numbered $0, 1, \dots$ in the order they are given.

The next $P$ lines each describe a customer parcel as a real number $t$ and three integers $w$ $d$ $v$: timestamp $t$, weight $w$ kg, destination airport $d$, and value $v$ dollars. These lines are in increasing timestamp order.

The next $B$ lines describe the parcels already in the loading bay, in the same format and also in increasing timestamp order.

Every value on a line is separated by a single space. The input ends with a line 0 0 0 0 0, which must not be processed.

Constraints: $1 \le A \le 30$, $1 \le F \le 100$, $0 \le P + B \le 5000$, $1 \le C \le 150$.

For each loading problem, and for each flight that leaves airport $0$, print one line in increasing flight-number order, in the form Flight <n> value = <v>, where <n> is the flight's number and <v> is the total value of the parcels loaded onto that flight.