Problem
Một trong những đội tham gia Olympic đã quyết định trở về nhà bằng tàu hỏa. Đồng thời, các chàng trai muốn về nhà càng sớm càng tốt. Thật không may, không phải tất cả các chuyến tàu điện đều đi từ thành phố nơi tổ chức Thế vận hội đến nhà ga nơi các chàng trai sinh sống. Và, điều thậm chí còn gây khó chịu hơn, không phải tất cả các chuyến tàu điện đi qua ga của họ đều dừng lại ở đó (cũng như nói chung, các chuyến tàu điện không dừng lại ở tất cả các ga mà họ đi qua).
Tất cả các trạm trên đường được đánh số từ 1 đến N. Đồng thời, trạm số 1 nằm ở thành phố tổ chức Olympic, lúc 0 các bạn đến trạm. Nhà ga mà các chàng trai cần đến có số E.
Viết một chương trình, cho trước một lịch trình xe lửa, tính toán thời gian tối thiểu mà những người đó có thể ở nhà.
Đầu vào
Trong tệp đầu vào các số N (2 ≤ N ≤ 100) và E (2 ≤ E ≤ N) được viết trước. Sau đó, số M (0 ≤ M ≤ 100) được viết, cho biết số lần tàu chạy. Sau đây là mô tả M hành trình của tàu điện. Mô tả của mỗi chuyến tàu bắt đầu bằng số Ki (2 ≤ Ki ≤ N) — số trạm mà nó dừng lại, theo sau là cặp số Ki, số đầu tiên của mỗi cặp chỉ định số trạm, số thứ hai — thời gian tàu dừng tại ga này (thời gian được biểu thị dưới dạng số nguyên từ 0 đến 109). Các trạm trong cùng một chuyến bay được sắp xếp theo thứ tự thời gian tăng dần. Trong một hành trình, đoàn tàu luôn di chuyển theo cùng một hướng — ra khỏi thành phố hoặc hướng tới thành phố.
Đầu ra
Để xuất tệp in một số — thời gian tối thiểu khi các chàng trai có thể ở trạm của họ. Nếu họ không thể đến đó bằng các tuyến tàu hiện có, hãy in –1.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
5 2
2
4 1 1 3 2 4 10 5 20
3 5 10 4 15 2 40
|
40 |