Mệt mỏi vì thời tiết mùa đông lạnh giá ở trang trại, cô bò Bessie dự định bay đến một nơi ấm áp hơn để nghỉ dưỡng. Đáng tiếc, cô phát hiện ra rằng chỉ có một hãng hàng không, Air Bovinia, sẵn lòng bán vé cho bò, và cấu trúc của những tấm vé này lại khá phức tạp.

Air Bovinia sở hữu \(N\) máy bay (\(1 \le N \le 500\)), mỗi chiếc bay theo một "tuyến" cố định gồm hai thành phố trở lên. Chẳng hạn, một máy bay có thể bay theo tuyến bắt đầu tại thành phố 1, sau đó đến thành phố 5, tiếp theo đến thành phố 2 và cuối cùng đến thành phố 8. Không thành phố nào xuất hiện nhiều lần trên một tuyến. Nếu Bessie chọn sử dụng một tuyến, cô có thể lên máy bay tại bất kỳ thành phố nào trên tuyến rồi xuống tại bất kỳ thành phố nào nằm sau đó trên tuyến. Cô không nhất thiết phải lên tại thành phố đầu tiên hay xuống tại thành phố cuối cùng. Mỗi tuyến có một chi phí nhất định mà Bessie phải trả nếu sử dụng bất kỳ phần nào của tuyến, bất kể cô đi qua bao nhiêu thành phố trên tuyến đó.

Bessie muốn tìm cách rẻ nhất để đi từ trang trại của mình (ở thành phố \(A\)) đến điểm đến nhiệt đới (thành phố \(B\)). Vì không muốn bị rối bởi một hành trình phức tạp, cô chỉ muốn sử dụng đúng một tuyến. Hãy giúp cô xác định chi phí tối thiểu phải trả.

Dữ liệu vào

Dòng đầu tiên chứa \(A\), \(B\) và \(N\), cách nhau bởi dấu cách.

\(2N\) dòng tiếp theo mô tả các tuyến hiện có, mỗi tuyến bằng hai dòng. Dòng đầu tiên chứa chi phí sử dụng tuyến (một số nguyên trong đoạn \(1\ldots1000\)) và số thành phố trên tuyến (một số nguyên trong đoạn \(1\ldots500\)). Dòng thứ hai chứa danh sách các thành phố theo thứ tự trên tuyến. Mỗi thành phố được xác định bằng một số nguyên trong đoạn \(1\ldots10\,000\).

Dữ liệu ra

In chi phí nhỏ nhất của một tuyến duy nhất mà Bessie có thể sử dụng để đi từ thành phố \(A\) đến thành phố \(B\). Nếu không có tuyến nào như vậy, in -1.

Ví dụ

1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 2

8

Nguồn

USACO 2015 January Contest, Bronze - Cow Routing: https://usaco.org/index.php?page=viewproblem2&cpid=507

Tác giả: Richard Peng, 2015.