Un agent secret are o hartă pe care sunt marcate $N$ obiective militare. El se află, iniţial, lângă obiectivul numerotat cu $1$ (baza militară proprie) şi trebuie să ajungă la obiectivul numerotat cu $N$ (baza militară inamică). În acest scop, el va folosi drumurile existente, fiecare drum legând $2$ obiective distincte. Fiind o misiune secretă, deplasarea agentului va avea loc noaptea; de aceea, el are nevoie de o lanternă. Pentru aceasta, el are de ales intre $K$ tipuri de lanterne – o lanternă de tipul $W$ ($1 \leq W \leq K$) are baterii care permit consumul a $W$ waţi, după consumul acestor waţi, lanterna nu mai luminează. Din fericire, unele dintre obiective sunt baze militare prietene, astfel că, o dată ajuns acolo, el îşi poate reîncărca bateriile complet. Agentul trebuie sa aibă grijă ca, înainte de a merge pe un drum între două obiective, cantitatea de waţi pe care o mai poate consuma să fie mai mare sau egală cu cantitatea de waţi pe care o va consuma pe drumul respectiv.

Cunoscând drumurile dintre obiective şi, pentru fiecare drum, durata necesară parcurgerii drumului şi numărul de waţi consumaţi de lanternă, determinaţi tipul de lanternă cu numărul cel mai mic, astfel încât durata deplasării sa fie minimă (dintre toate tipurile de lanternă cu care se poate ajunge în timp minim la destinaţie, interesează lanterna cu consumul cel mai mic).

Date de intrare

Pe prima linie a fişierului lanterna.in se află numerele întregi $N$ şi $K$, separate printr-un spaţiu. Pe următoarea linie se află $N$ numere întregi din mulţimea ${0,1}$. Daca al $i$-lea număr este $1$, aceasta înseamnă că obiectivul cu numărul $i$ este o bază militară prietenă (adică agentul îşi poate reîncărca bateriile lanternei daca ajunge la acest obiectiv); dacă numărul este $0$, agentul nu îşi va putea reîncărca bateriile. Primul număr din linie este $1$, iar ultimul este $0$. Pe cea de-a treia linie a fişierului se află numărul $M$ de drumuri dintre obiective. Fiecare din următoarele $M$ linii conţine câte $4$ numere întregi separate prin spaţii: $a\ b\ T\ W$ , având semnificaţia că există un drum bidirecţional între obiectivele $a$ şi $b$ ($a≠b$), care poate fi parcurs într-un timp $T$ şi cu un consum de $W$ waţi.

Date de ieşire

In fişierul lanterna.out se vor afişa două numere întregi, separate printr-un spaţiu : $T_{min}$ şi $W_{min}$. $T_{min}$ reprezentând durata minimă posibilă a deplasării de la obiectivul $1$ la obiectivul $N$, iar $W_{min}$ reprezintă tipul de lanternă cu numărul cel mai mic pentru care se obţine acest timp.

Restricţii şi precizări

• $2 ≤ N ≤ 50$
• $1 ≤ K ≤ 1 \ 000$
• $1 ≤ M ≤ N(N-1)/2$
• Între două oraşe diferite poate exista maximum un drum direct.
• Pentru fiecare drum, durata parcurgerii este un număr întreg intre $1$ şi $100$, iar numărul de waţi consumaţi este un număr întreg între $0$ şi $1 000$
• Se garantează că există cel puţin un tip de lanternă pentru care deplasarea să fie posibilă.
• Punctajul pentru un test se va acorda in felul următor:
• 30% daca este determinat corect $T_{min}$
• 100% daca sunt determinate corect atât $T_{min}$, cât şi $W_{min}$

Exemplu

lanterna.in

7 10
1 0 1 0 0 0 0
7
1 2 10 3
1 4 5 5
2 3 10 3
4 3 15 1
3 6 4 3
6 5 2 2
5 7 1 0

lanterna.out

27 6