27523번 - 신촌방위본부 탈출

지난 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$)

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

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