Vasile vrea să meargă în vacanţă la bunici cu trenul. Există N staţii pe calea ferată, numerotate în ordinea în care se află pe traseu de la 1 la N. Staţia 1 este în oraşul în care locuieşte Vasile (staţia de plecare), iar staţia destinaţie (din oraşul în care locuiesc bunicii) este X.
În gară este afişat mersul trenurilor. În mersul trenurilor sunt descrise traseele a M trenuri. Un traseu este specificat precizând numărul de staţii în care opreşte trenul Nr, apoi sunt specificate Nr perechi de numere naturale. Primul număr din pereche este numărul staţiei, iar cel de-al doilea momentul de timp la care ajunge trenul în staţia respectivă. Pe orice traseu, staţiile sunt specificate în ordinea crescătoare a timpilor de sosire. Un tren parcurge traseul într-un singur sens (fie în sensul de la staţia 1 la staţia N, fie în sens invers).
Vasile soseşte în gară la momentul 0.

Cerinţă

Determinaţi timpul minim în care Vasile poate ajunge la bunici cu trenul.

Date de intrare

Fişierul de intrare bunici.in conţine pe prima linie două numere naturale N şi X reprezentând numărul de staţii şi respectiv staţia destinaţie. Pe a doua linie este scris un număr natural M reprezentând numărul de trenuri. Pe următoarele M linii se află traseele celor M trenuri, câte un traseu pe o linie, conform specificaţiilor din enunţ. Numerele scrise pe aceeaşi linie sunt separate prin spaţii.

Date de ieşire

Fişierul de ieşire bunici.out va conţine o singură linie, pe care va fi scris un singur număr natural, reprezentând timpul minim în care Vasile poate ajunge la bunici.

Restricţii

• 2<=N<=100
• 1<=M<=100
• Timpii de sosire în staţii sunt numere naturale <=10⁹
• Pentru datele de test există întotdeauna soluţie.

Exemple

bunici.in	bunici.out	Explicatie
5 3 4 2 1 5 2 10 2 2 10 4 15 4 5 0 4 17 3 20 2 35 3 1 2 3 40 4 45	20	Din orasul 1 pleaca la momentul 5 cu trenul 1, ajunge in orasul 2 la momentul 10. Din orasul 2 pleaca la momentul 10 cu trenul 2, ajunge la momentul 15 in orasul 4. Din orasul 4 pleaca la momentul 17 cu trenul 3 si ajunge in orasul 3 la momentul 20 (minim posibil).

prof. Emanuela Cerchez

Liceul de Informatică „Grigore Moisil” Iaşi

emanuela.cerchez@gmail.com