Đề bài

Có ~N~ thành phố và ~M~ đường hàng không hai chiều giữa một số cặp thành phố nào đó, các đường bay được quản lý bởi ~x~ (~1 \leq x \leq 16~) hãng hàng không. Các thành phố được đánh số từ ~1~ tới ~N~ (~N \leq 100~) và các hãng được đánh số từ ~1~ tới ~x~.

Được biết chi phí bay trực tiếp giữa hai thành phố ~i, j~ bất kỳ (nếu như có đường bay) là ~C~. Nếu đang đi máy bay của một hãng đến sân bay nào đó rồi chuyển sang máy bay của hãng khác thì sẽ phải mất thêm một khoản phụ phí ~A~.

Yêu cầu: Cho trước hai thành phố ~S~ và ~F~, hãy tìm hành trình bay từ thành phố ~S~ đến thành phố ~F~ với chi phí ít nhất. Với giả thiết rằng luôn luôn tồn tại cách bay từ ~S~ tới ~F~.

Input

• Dòng 1 ghi sáu số nguyên dương ~N, M, C, A, S, F~ (~1 \leq A, C \leq 100~)
• ~M~ dòng tiếp theo, mỗi dòng có dạng ~u\ v\ k\ x_1\ x_2\ \dots\ x_k~ cho biết rằng giữa thành phố ~u~ và thành phố ~v~ có ~k~ đường bay và ~x_1, x_2, \dots, x_k~ là số hiệu các hãng sở hữu đường bay đó.

Output

• Một dòng duy nhất là chi phí tối thiểu phải trả.

Ví dụ

Sample Input 1

15 16 3 2 1 5
1 2 1 1
2 3 1 1
3 4 2 1 2
3 9 1 2
4 9 1 1
5 10 2 1 3
6 7 1 1
6 11 1 1
7 8 1 1
7 13 1 2
8 9 1 1
10 15 1 3
11 12 1 1
12 13 1 1
13 14 2 1 3
14 15 2 1 3

Sample Output 1

37

Giới hạn

• Thời gian: ~2.0s~
• Bộ nhớ: ~256M~
• ~1 \leq x \leq 16~
• ~N \leq 100~

Subtasks

• Subtask 1: Có ~25%~ số test đầu tiên các tuyến bay được quản lý bởi cùng một hãng hàng không;
• Subtask 2: Có ~25%~ số test tiếp theo các tuyến bay được bố trí dưới dạng thành phố ~i~ chỉ có ~2~ tuyến bay đến thành phố ~i - 1~ và ~i + 1~, trừ thành phố ~1~ chỉ có tuyến bay đến thành phố ~2~ và thành phố ~n~ chỉ có tuyến bay đến thành phố ~n - 1~;
• Subtask 3: Có ~50%~ số test cuối cùng không có ràng buộc gì.

Giải thích ví dụ

Với mạng lưới đường không như hình minh họa (trang 2 ): cần đi từ thành phố ~1~ đến thành phố ~5~. Chi phí đường bay trực tiếp giữa hai thành phố bất kỳ ~C = 3~, phụ phí chuyển tuyến ~A = 2~. Các số ghi bên cạnh các đường bay trực tiếp là tên các hãng sở hữu đường bay đó.