Problem
Uma das equipes participantes da Olimpíada decidiu voltar para casa de trem. Ao mesmo tempo, os caras querem voltar para casa o mais rápido possível. Infelizmente, nem todos os trens elétricos vão da cidade onde acontece a Olimpíada até a estação onde moram os caras. E, o que é ainda mais ofensivo, nem todos os trens elétricos que passam por sua estação param nela (assim como, em geral, os trens elétricos não param em todas as estações por onde passam).
Todas as estações da linha são numeradas de 1 a N. Ao mesmo tempo, a estação número 1 fica na cidade onde é realizada a Olimpíada, e no horário 0 os caras chegam à estação. A estação que os caras precisam chegar tem o número E.
Faça um programa que, dado um horário de trem, calcule o tempo mínimo que os caras podem ficar em casa.
Entrada
No arquivo de entrada os números N (2 ≤ N ≤ 100) e E (2 ≤ E ≤ N) são escritos primeiro. Em seguida, o número M (0 ≤ M ≤ 100) é escrito, indicando o número de passagens do trem. A seguir está uma descrição de M viagens de trens elétricos. A descrição de cada voo de trem começa com o número Ki (2 ≤ Ki ≤ N) — o número de estações em que ele para, seguido por Ki pares de números, o primeiro número de cada par especifica o número da estação, o segundo — hora em que o trem para nesta estação (a hora é expressa como um número inteiro de 0 a 109). As estações dentro do mesmo voo são ordenadas em ordem crescente de tempo. Durante uma viagem, o trem se move na mesma direção o tempo todo — longe da cidade ou em direção à cidade.
Saída
Para o arquivo de saída imprimir um número — o tempo mínimo em que os caras podem estar em sua estação. Se eles não puderem chegar lá pelas rotas de trem existentes, imprima –1.
Exemplos
| # |
Entrada |
Saída |
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |