신촌방위본부 탈출

지난 2021년 8월 21일, 신촌방위본부는 정체불명의 조직의 공격을 받았다. 신촌방위본부는 이를 훌륭한 대처로 막아냈지만, 정체불명의 조직은 이를 잊지 않고 다시 공격할 때를 기다리고 있었다. 2023년 2월 25일, 2년간의 기다림 끝에 정체불명의 조직은 신촌방위본부 건물을 직접 타격했고, 그 결과 본부 건물에 화재가 발생했다. 신촌방위본부 사령관인 당신은 화재로부터 최대한 많은 인원을 대피시키려 한다.

신촌방위본부는 $N$개의 건물과 이를 잇는 $M$개의 양방향 복도로 이루어진 연결 그래프이며, 각 건물은 $1$번부터 $N$번까지 번호가 붙어 있다. 같은 건물 쌍을 잇는 복도가 여러 개 있을 수도 있다. 불이 처음 난 건물은 $1$번 건물이며, 탈출구는 $N$번 건물에 있다. $N$번 건물에서 탈출하는 데 걸리는 시간은 매우 짧아 $0$으로 생각할 수 있다. 각 건물은 불이 처음 붙은 지 $1$시간 후, 복도로 연결되어 있으면서 아직 불이 붙지 않은 모든 건물에 불을 옮긴다. 불이 붙고 $T$시간이 지난 건물은 완전히 무너져 사람이 지나갈 수 없다. 정확히 $T$시간이 지난 시점에도 건물에 연결된 복도나 탈출구로 입장할 수 없다.

초기에 $i$번 건물에는 $P_i$명의 사람이 있다. 사람은 복도를 통해 이동할 수 있으며, 복도에는 각 시간마다 한 번에 입장할 수 있는 최대 인원 $c$, 복도를 통해 이동하는 데 드는 시간 $t$, 복도에 입장할 때 1명당 증가하는 피로도 $x$가 있다.

당신의 목표는 최대한 많은 인원을 최단 탈출 시간 내에 최소한의 피로도 총합으로 대피시키는 것이다. 우선순위는 인원, 탈출 시간, 피로도 순이다. 탈출 시간은 마지막으로 탈출한 사람이 탈출한 시간을 뜻하며, 탈출한 인원이 0명이면 0이다.

첫째 줄에 건물의 수 $N$, 복도의 수 $M$, 건물이 완전히 무너지는 데 걸리는 시간 $T$가 공백으로 구분되어 주어진다. ($2 \leq N \leq 50; 1 \leq T \leq 50; 1 \leq M \leq 200$)

둘째 줄에 $i$번 건물에 있는 사람의 수 $P_i$가 공백으로 구분되어 주어진다. ($0 \leq P_i \leq 100; \sum_{i=1}^N P_i \leq 100$)

셋째 줄부터 $M$개의 줄에 걸쳐 $i$번째 복도의 정보 $u_i, v_i, c_i, t_i, x_i$가 공백으로 구분되어 주어진다.

이는 $u_i$번 건물과 $v_i$번 건물을 잇는 복도가 지문에서 설명한 $c_i, t_i, x_i$ 값을 가진다는 뜻이다. ($1 \leq u_i, v_i \leq N; 1 \leq c_i, t_i, x_i \leq 100; u_i \neq v_i$)

주어지는 수는 모두 정수이다.

대피시킬 수 있는 최대 인원수, 최대 인원수를 대피시킬 수 있는 최단 탈출 시간, 최대 인원을 최단 탈출 시간에 대피시킬 때의 최소 피로도 총합을 공백으로 구분하여 한 줄에 출력한다.