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 chỉ có thể sử dụng mỗi tuyến một lần (nghĩa là cô không thể dùng một tuyến rồi sau đó lại dùng một phần khác của chính tuyến ấy).

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ô muốn sử dụng nhiều nhất hai tuyến. Hãy giúp cô xác định chi phí tối thiểu phải trả.

Lưu ý rằng điểm khác biệt duy nhất giữa bài này và bài Bronze ngay trước đó là trong bài này Bessie có thể sử dụng tối đa hai tuyến, thay vì chỉ một tuyến như trong bài trước.

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 hành trình sử dụng nhiều nhất hai tuyến mà Bessie có thể dùng để đi từ thành phố \(A\) đến thành phố \(B\). Nếu không có phương á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

7

Nguồn

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

Tác giả: Richard Peng và Brian Dean, 2015.