Problem
Una delle squadre partecipanti alle Olimpiadi ha deciso di tornare a casa in treno. Allo stesso tempo, i ragazzi vogliono tornare a casa il prima possibile. Sfortunatamente, non tutti i treni elettrici vanno dalla città in cui si svolgono le Olimpiadi alla stazione in cui vivono i ragazzi. E, cosa ancora più offensiva, non tutti i treni elettrici che passano davanti alla loro stazione vi si fermano (così come in generale i treni elettrici non si fermano in tutte le stazioni in cui passano).
Tutte le stazioni della linea sono numerate da 1 a N. Allo stesso tempo, la stazione numero 1 si trova nella città in cui si svolgono le Olimpiadi, e all'ora 0 i ragazzi arrivano alla stazione. La stazione a cui i ragazzi devono arrivare ha il numero E.
Scrivi un programma che, dato un orario dei treni, calcoli il tempo minimo in cui i ragazzi possono essere a casa.
Input
Nel file di input i numeri N (2 ≤ N ≤ 100) ed E (2 ≤ E ≤ N) sono scritti per primi. Quindi viene scritto il numero M (0 ≤ M ≤ 100), che indica il numero di corse del treno. Quanto segue è una descrizione di viaggi M di treni elettrici. La descrizione di ogni volo ferroviario inizia con il numero Ki (2 ≤ Ki ≤ N) — il numero di stazioni in cui si ferma, seguito da Ki coppie di numeri, il primo numero di ciascuna coppia specifica il numero della stazione, il secondo — ora in cui il treno si ferma in questa stazione (l'ora è espressa come numero intero da 0 a 109). Le stazioni all'interno dello stesso volo sono ordinate in ordine crescente di tempo. Durante un viaggio, il treno si muove sempre nella stessa direzione — o lontano dalla città o verso la città.
Uscita
Per generare il file stampa un numero — il tempo minimo in cui i ragazzi possono essere alla loro postazione. Se non possono arrivarci con le linee ferroviarie esistenti, stampa –1.
Esempi
| # |
Input |
Uscita |
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |