Sinchon Defense HQ Escape

On August 21, 2021, the Sinchon Defense Headquarters was attacked by an unknown organization. The headquarters repelled the attack with a strong response, but the organization did not forget and waited for a chance to strike again. On February 25, 2023, after two years of waiting, the organization hit the headquarters building directly, and a fire broke out inside it. As the commander of the Sinchon Defense Headquarters, you want to evacuate as many people as possible from the fire.

The headquarters is a connected graph of $N$ buildings and $M$ two-way corridors that link them. The buildings are numbered from $1$ to $N$. Several corridors may connect the same pair of buildings. The fire starts in building $1$, and the exit is in building $N$. Leaving through building $N$ takes so little time that it can be treated as $0$. One hour after a building catches fire, it passes the fire to every connected building that has not yet caught fire through a corridor. A building collapses completely $T$ hours after it catches fire, and no one can pass through it. People cannot enter a corridor connected to a building, or the exit, even at exactly $T$ hours after the fire starts.

Initially, building $i$ has $P_i$ people. People move through corridors. Each corridor has a capacity $c$, which is the maximum number of people that can enter it in one hour, a travel time $t$, and a fatigue value $x$, which increases by $1$ for each person entering it.

Your goal is to evacuate the largest possible number of people in the shortest possible escape time with the smallest total fatigue. These goals are ranked in that order: number of people, then escape time, then fatigue. The escape time is the time when the last person escapes, and it is $0$ if no one escapes.

The first line contains the number of buildings $N$, the number of corridors $M$, and the time $T$ it takes for a building to collapse completely, separated by spaces. ($2 \leq N \leq 50; 1 \leq T \leq 50; 1 \leq M \leq 200$)

The second line contains the number of people $P_i$ in building $i$, separated by spaces. ($0 \leq P_i \leq 100; \sum_{i=1}^N P_i \leq 100$)

From the third line, $M$ lines follow. The $i$-th line contains $u_i, v_i, c_i, t_i, x_i$, separated by spaces.

This means that the corridor connecting building $u_i$ and building $v_i$ has the values $c_i$, $t_i$, and $x_i$ described above. ($1 \leq u_i, v_i \leq N; 1 \leq c_i, t_i, x_i \leq 100; u_i \neq v_i$)

All given numbers are integers.

Print the maximum number of people that can be evacuated, the shortest escape time for evacuating that maximum number of people, and the minimum total fatigue when evacuating the maximum number of people in the shortest escape time, separated by spaces on one line.