Chuyến Bay Giá Rẻ II

Có $N$ chuyến bay, mỗi chuyến bay đi qua một số thành phố theo thứ tự cố định và có chi phí cố định. Bạn muốn đi từ thành phố $A$ đến thành phố $B$ bằng tối đa hai chuyến bay: mỗi chuyến bay bạn lên ở một điểm dừng và xuống ở một điểm dừng sau đó.

Tìm tổng chi phí nhỏ nhất, hoặc $-1$ nếu không thể đến được.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $A$, $B$, $N$.

• $N$ dòng tiếp theo, mỗi dòng mô tả một chuyến bay: số nguyên $C$ (chi phí) và $K$ (số thành phố), tiếp theo là $K$ số nguyên là thứ tự các thành phố trên lộ trình.

Dữ liệu ra

Một số nguyên — tổng chi phí nhỏ nhất, hoặc $-1$ nếu không thể đến được.

Ràng buộc

• $1\le N\le 500$
• $1\le C\le 1000$
• $2\le K\le 500$
• Số hiệu thành phố từ $1$ đến $10000$

Ví dụ