Das Land IOI besteht aus $N$ Städten, von Stadt $1$ bis Stadt $N$, und die Städte sind durch Straßen miteinander verbunden. Im Land IOI gibt es $K$ Straßen, und jede Straße verbindet $2$ verschiedene Städte. Autos können sich auf den Straßen frei in beide Richtungen bewegen, aber man kann nicht außerhalb der Straßen von einer Stadt in eine andere gelangen.

JOI-kun, der in Stadt $1$ im Land IOI lebt, hat beschlossen, mit dem Taxi zum Haus seiner Großmutter in Stadt $N$ zu fahren. Im Land IOI gibt es $N$ Taxiunternehmen, von Taxiunternehmen $1$ bis Taxiunternehmen $N$. Für die Taxiunternehmen im Land IOI gelten die folgenden etwas speziellen Regeln:

• In ein Taxi des Taxiunternehmens $i$ kann man nur in Stadt $i$ einsteigen.
• Der Fahrpreis eines Taxis des Taxiunternehmens $i$ beträgt unabhängig von der zurückgelegten Strecke $C_i$.
• Ein Taxi des Taxiunternehmens $i$ kann nach dem Einsteigen hintereinander höchstens $R_i$ Straßen befahren.

Wenn zum Beispiel $R_1 = 2$ gilt und man in Stadt $1$ in ein Taxi des Taxiunternehmens $1$ einsteigt, kann man höchstens $2$ Straßen befahren; um $3$ oder mehr Straßen zu befahren, muss man daher in einer Zwischenstadt in ein anderes Taxi umsteigen.

JOI-kun kann an keinem Ort außerhalb einer Stadt in ein Taxi einsteigen oder aus einem Taxi aussteigen. Außerdem kann er kein anderes Verkehrsmittel als Taxis benutzen. Schreibe ein Programm, das das Minimum der Gesamtfahrkosten bestimmt, die JOI-kun benötigt, um Stadt $N$ zu erreichen.

Eingabe

Die Eingabe besteht aus $1 + N + K$ Zeilen.

In der $1$. Zeile stehen $2$ durch ein Leerzeichen getrennte ganze Zahlen $N, K$ ($2 \le N \le 5000$, $N - 1 \le K \le 10000$). Dies bedeutet, dass das Land IOI aus $N$ Städten besteht und dass die Anzahl der Straßen im Land IOI $K$ beträgt.

In der $i$-ten Zeile ($1 \le i \le N$) der folgenden $N$ Zeilen stehen $2$ durch ein Leerzeichen getrennte ganze Zahlen $C_i, R_i$ ($1 \le C_i \le 10000$, $1 \le R_i \le N$). Dies bedeutet, dass der Fahrpreis eines Taxis des Taxiunternehmens $i$ gleich $C_i$ ist und es nach dem Einsteigen hintereinander höchstens $R_i$ Straßen befahren kann.

In der $j$-ten Zeile ($1 \le j \le K$) der folgenden $K$ Zeilen stehen $2$ verschiedene, durch ein Leerzeichen getrennte ganze Zahlen $A_j, B_j$ ($1 \le A_j < B_j \le N$). Dies bedeutet, dass zwischen Stadt $A_j$ und Stadt $B_j$ eine Straße existiert. Dasselbe Paar $(A_j, B_j)$ kommt nicht $2$-mal oder öfter vor.

In den gegebenen Eingabedaten ist garantiert, dass man von jeder Stadt in jede andere Stadt durch Umsteigen zwischen Taxis gelangen kann.

Ausgabe

Gib in $1$ Zeile eine ganze Zahl aus, die das Minimum der Gesamtfahrkosten angibt, die JOI-kun benötigt, um von Stadt $1$ nach Stadt $N$ zu gelangen.

Beispiele

Eingabe 1

6 6
400 2
200 1
600 3
1000 1
300 5
700 4
1 2
2 3
3 6
4 6
1 5
2 4

Ausgabe 1

700

Hinweis

Das obige Beispiel entspricht der folgenden Abbildung. Kreise stellen Städte und Linien stellen Straßen dar.

Um in diesem Beispiel mit minimalem Fahrpreis nach Stadt $6$ zu gelangen, geht JOI-kun wie folgt vor:

• Er nimmt in Stadt $1$ ein Taxi und fährt nach Stadt $5$. (Fahrpreis $400$)
• Er nimmt in Stadt $5$ ein Taxi und fährt nach Stadt $6$. (Fahrpreis $300$)

Da die Summe der Fahrpreise auf dieser Route $400 + 300 = 700$ beträgt, ist $700$ auszugeben.