항공 우편 배송 (Packages Par Avion)

어느 배송 회사의 0번 공항에서 항공 우편 시스템을 운영한다고 하자. 이 회사는 접수 창구와, 공항 사이를 오가는 항공기 편대를 운영하며, 소포가 배송지에서 가장 가까운 공항에 도착하면 별도의 지상 운송 회사가 최종 배송을 맡는다. 매일 당신은 0번 공항을 떠나는 항공기에 어떤 소포를 실을지 결정해야 한다.

하루의 흐름은 다음과 같다.

• 접수. 손님들이 0번 공항에 소포를 가져온다. 각 소포에는 (이미 올림한) 정수 무게(kg), 목적지 공항(배송지에서 가장 가까운 공항), 타임스탬프, 그리고 달러 단위 가치가 있다. 소포는 타임스탬프가 증가하는 순서로 도착하며 모든 타임스탬프는 서로 다르다. 접수 구역이 담을 수 있는 총 무게는 최대 $C$ kg이다. 그날 들어온 소포를 타임스탬프 순서대로 처리하되, 지금까지 받아들인 무게의 합이 $C$ 이하로 유지될 때에만 그 소포를 받아들이고, 그렇지 않으면 거절한다. 무거운 소포가 거절된 뒤에도 더 가벼운 소포는 여전히 받아들여질 수 있다.
• 적재장. 접수가 끝나면 받아들인 모든 소포는 이미 0번 공항 적재장에 있던 소포들(이전 날짜에서 남았거나, 여러 구간 경로의 중간에 있는 소포들)과 합쳐진다. 각 공항은 자기 적재장에 현재 있는 소포들의 총 무게를 알려 준다.
• 다음 경유지 선택. 0번 공항 적재장의 각 소포에 대해, 오늘의 항공편을 이용해 0번 공항에서 그 소포의 목적지로 가는 경로들을 생각하고, 항공편 수(홉 수)가 가장 적은 경로를 고른다. 가장 짧은 경로가 여럿이면, 그 첫 항공편의 도착 공항 중 적재장 총 무게가 가장 작은 곳으로 가는 경로를 택한다. 그래도 같으면 공항 번호가 더 작은 쪽을 택한다. 소포의 다음 경유지는 선택된 경로의 첫 공항이다. 목적지에 도달할 수 없으면 소포는 적재장에 남는다.
• 항공기 적재. 0번 공항을 떠나는 각 항공기는 다음 경유지가 그 항공기의 도착지인 소포들을, 항공기의 무게 용량(kg) 한도 안에서 실을 수 있다. 이 소포들 중 총 가치가 최대가 되는 부분집합을 고른다(무게에 대한 0/1 배낭 문제). 최대 가치에 도달하는 부분집합이 여럿이어도 보고하는 총 가치는 달라지지 않으므로 그중 어느 것을 실어도 된다. 싣지 못한 소포는 다음 날을 기다린다.

0번 공항을 떠나는 각 항공편에 대해, 그 항공편에 실린 소포들의 총 가치를 출력하라.

입력은 여러 개의 독립적인 적재 문제로 이루어진다. 각 문제는 다섯 정수 $A$ $F$ $P$ $B$ $C$가 있는 줄로 시작한다.

• $A$ — 다른 공항의 수로, $1$번부터 $A$번까지 번호가 매겨진다(당신의 공항은 $0$번이다);
• $F$ — 오늘의 항공편 수;
• $P$ — 오늘 손님이 가져온 소포 수;
• $B$ — 이미 적재장에 있는 소포 수;
• $C$ — 접수 구역의 무게 용량.

다음 $A$개의 줄에는 각각 정수 하나가 있으며, 공항 $1, 2, \dots, A$의 적재장 총 무게를 이 순서대로 나타낸다.

다음 $F$개의 줄은 각각 세 정수 $s$ $d$ $c$로 항공편을 나타낸다. 즉 공항 $s$에서 공항 $d$로 날아가며 최대 $c$ kg을 실을 수 있다. 공항 $0$은 당신의 공항이며, 순서 있는 공항 쌍마다 항공편은 최대 하나이다. 항공편은 주어진 순서대로 $0, 1, \dots$로 번호가 매겨진다.

다음 $P$개의 줄은 각각 실수 $t$와 세 정수 $w$ $d$ $v$로 손님 소포를 나타낸다: 타임스탬프 $t$, 무게 $w$ kg, 목적지 공항 $d$, 가치 $v$ 달러. 이 줄들은 타임스탬프가 증가하는 순서이다.

다음 $B$개의 줄은 이미 적재장에 있는 소포들을 같은 형식으로, 역시 타임스탬프가 증가하는 순서로 나타낸다.

한 줄의 모든 값은 공백 하나로 구분된다. 입력은 0 0 0 0 0인 줄로 끝나며, 이 줄은 처리하지 않는다.

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

각 적재 문제에 대해, 그리고 공항 $0$을 떠나는 각 항공편에 대해, 항공편 번호가 증가하는 순서로 Flight <n> value = <v> 형식의 줄을 하나씩 출력한다. 여기서 <n>은 항공편 번호이고 <v>는 그 항공편에 실린 소포들의 총 가치이다.