Problem
Eines der teilnehmenden Teams beschloss, mit dem Zug nach Hause zurückzukehren. Dabei wollen die Jungs so früh wie möglich nach Hause kommen. Leider fahren nicht alle Züge von der Stadt, in der die Olympischen Spiele stattfinden, bis zur Station, in der die Kinder leben. Und, noch beleidigender, nicht alle Züge, die an ihrer Station vorbeifahren, halten dort an (wie im Allgemeinen halten die Züge nicht an allen Stationen, an denen sie vorbeifahren).
Alle Stationen auf der Linie sind mit Zahlen von 1 bis N nummeriert. Dabei befindet sich Station Nummer 1 in der Stadt, in der die Olympischen Spiele stattfinden, und zur Zeit 0 kommen die Jungs zum Bahnhof. Die Station, zu der die Jungs gelangen müssen, hat die Nummer E.
Schreiben Sie ein Programm, das nach diesem Fahrplan die minimale Zeit berechnet, in der die Jungs zu Hause sein können.
Eingabe
In der Eingabedatei werden zuerst die Zahlen N (2 ≤ N ≤ 100) und E (2 ≤ E ≤ N) geschrieben. Dann wird die Zahl M (0 ≤ M ≤ 100) aufgezeichnet, die die Anzahl der Züge angibt. Als nächstes kommt die Beschreibung von M-S-Bahn-Flügen. Die Beschreibung der einzelnen Züge beginnt mit der Nummer Ki (2 ≤ Ki ≤ N), gefolgt von den Zahlenpaaren Ki, wobei die erste Zahl jedes Zugpaares die Nummer der Station angibt, die zweite Zeit, zu der der Zug an dieser Station angehalten wird (die Zeit wird durch eine ganze Zahl zwischen 0 und 109 ausgedrückt). Die Stationen innerhalb eines Fluges sind in aufsteigender Reihenfolge der Zeit angeordnet. Während eines Fluges bewegt sich die S-Bahn ständig in die gleiche Richtung, entweder von der Stadt oder in die Stadt.
Ausgabe
Geben Sie in die Ausgabedatei eine Zahl aus — die minimale Zeit, in der die Jungs auf ihrer Station sein können. Wenn sie die vorhandenen Züge nicht erreichen können, ziehen Sie bitte –1 aus.
Beispiele
| № |
Eingabe |
Ausgabe |
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |