Problem
L'une des équipes participant à l'Olympiade a décidé de rentrer chez elle en train. En même temps, les gars veulent rentrer chez eux au plus vite. Malheureusement, tous les trains électriques ne vont pas de la ville où se déroule l'Olympiade à la gare où vivent les gars. Et, ce qui est encore plus offensant, tous les trains électriques qui passent devant leur gare ne s'y arrêtent pas (ainsi qu'en général, les trains électriques ne s'arrêtent pas à toutes les gares qu'ils traversent).
Toutes les stations de la ligne sont numérotées de 1 à N. En même temps, la station numéro 1 est située dans la ville où se déroule l'Olympiade, et à l'heure 0, les gars arrivent à la station. La station à laquelle les gars doivent se rendre porte le numéro E.
Écrivez un programme qui, étant donné un horaire de train, calcule le temps minimum pendant lequel les gars peuvent être à la maison.
Entrée
Dans le fichier d'entrée les nombres N (2 ≤ N ≤ 100) et E (2 ≤ E ≤ N) sont écrits en premier. Ensuite, le nombre M (0 ≤ M ≤ 100) est écrit, indiquant le nombre de trajets du train. Ce qui suit est une description de trajets M de trains électriques. La description de chaque vol de train commence par le nombre Ki (2 ≤ Ki ≤ N) — le nombre de stations auxquelles il s'arrête, suivi de Ki paires de nombres, le premier nombre de chaque paire précise le numéro de la station, le second — l'heure à laquelle le train s'arrête à cette gare (l'heure est exprimée sous la forme d'un entier de 0 à 109). Les stations d'un même vol sont classées par ordre croissant de temps. Au cours d'un voyage, le train se déplace tout le temps dans le même sens — soit loin de la ville, soit vers la ville.
Sortie
Vers le fichier de sortie imprimer un numéro — le temps minimum pendant lequel les gars peuvent être à leur poste. S'ils ne peuvent pas s'y rendre par les itinéraires ferroviaires existants, écrivez –1.
Exemples
| # |
Entrée |
Sortie |
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
40 |