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 \le x \le 16)~ hãng hàng không. Các thành phố được đánh số từ ~1~ tới ~N~ ~(N \le 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 \le A, C \le 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ả.

Scoring

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

Notes

Với mạng lưới đường không như dưới đây: 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 đó.