Nhân dịp hè, Nam muốn đi từ nhà tới thăm ông bà. Mạng lưới xe khách của tỉnh có ~n~ bến xe, đánh số từ ~1~ đến ~n~, và có ~m~ tuyến xe. Mỗi tuyến chạy đúng một lượt trong ngày: tuyến thứ ~r~ lần lượt đi qua ~L_r~ bến ~b_{r,1}, b_{r,2}, \dots, b_{r,L_r}~ và tới bến ~b_{r,i}~ vào thời điểm ~t_{r,i}~. Dãy thời điểm dọc mỗi tuyến tăng ngặt, và hai bến liên tiếp trên một tuyến luôn khác nhau.

Nam lên được tuyến ~r~ tại bến ~b_{r,i}~ nếu có mặt ở bến đó vào một thời điểm không muộn hơn ~t_{r,i}~ (tới đúng lúc xe rời bến thì vẫn kịp lên xe). Sau đó Nam xuống ở một bến ~b_{r,j}~ nào đó với ~j > i~, vào thời điểm ~t_{r,j}~. Giá của lượt đi đó là ~\min((j-i) \times p_r, q_r)~, nghĩa là tính theo số chặng đã đi với đơn giá ~p_r~ một chặng, nhưng không bao giờ quá giá vé trọn tuyến ~q_r~. Nam được chờ ở một bến bao lâu tùy ý, và được lên xuống cùng một tuyến nhiều lần, mỗi lượt lên xuống trả tiền riêng.

Nam có mặt ở bến ~1~ từ thời điểm ~0~, còn nhà ông bà ở ngay cạnh bến ~n~. Đoàn trường cấp cho Nam ~k~ vé miễn phí; mỗi vé dùng được cho đúng một lượt đi (một lần lên rồi xuống), bất kể lượt đó dài bao nhiêu chặng. Nam không bắt buộc phải dùng hết số vé được cấp.

Hãy tính tổng số tiền ít nhất mà Nam phải trả để tới được bến ~n~.

Input

• Dòng đầu tiên: ba số nguyên ~n, m, k~ ~(2 \le n \le 10^5;\ 1 \le m \le 10^5;\ 0 \le k \le 10)~.

• Tiếp theo là ~m~ nhóm, mỗi nhóm ba dòng mô tả một tuyến. Nhóm thứ ~r~ gồm:

  • Dòng thứ nhất: ba số nguyên ~L_r, p_r, q_r~ ~(2 \le L_r;\ 1 \le p_r, q_r \le 10^9)~.

  • Dòng thứ hai: ~L_r~ số nguyên ~b_{r,1}, \dots, b_{r,L_r}~ ~(1 \le b_{r,i} \le n;\ b_{r,i} \ne b_{r,i+1})~.

  • Dòng thứ ba: ~L_r~ số nguyên ~t_{r,1}, \dots, t_{r,L_r}~ ~(0 \le t_{r,1} < t_{r,2} < \dots < t_{r,L_r} \le 10^9)~.

• Tổng số điểm dừng ~S = L_1 + L_2 + \dots + L_m~ không vượt quá ~10^5~. Có thể có nhiều tuyến trùng nhau hoàn toàn.

Output

In ra một số nguyên là tổng số tiền ít nhất mà Nam phải trả. Nếu Nam không thể tới được bến ~n~ thì in ra -1.

Scoring

Sample Input 1

5 3 0
3 9 15
1 2 3
0 2 5
2 7 7
1 3
0 9
3 3 90
3 4 5
5 6 8

Sample Output 1

21

Sample Input 2

4 3 1
2 8 8
1 2
0 2
3 5 9
2 3 4
2 4 6
2 100 100
1 3
0 3

Sample Output 2

5

Notes

Trong ví dụ thứ nhất, Nam không có vé miễn phí:

• Lên tuyến ~1~ ở bến ~1~ lúc ~0~, xuống ở bến ~3~ lúc ~5~: đi hai chặng, ~2 \times 9 = 18~ nhưng giá trọn tuyến chỉ ~15~ nên trả ~15~.

• Tuyến ~3~ rời bến ~3~ đúng lúc ~5~ nên Nam vẫn kịp lên, đi hai chặng tới bến ~5~ lúc ~8~, trả: ~\min(2 \times 3, 90) = 6~.

Tổng cộng ~15 + 6 = 21~. Nếu đi tuyến ~2~ (giá ~7~) thì Nam tới bến ~3~ lúc ~9~, đã lỡ tuyến ~3~.

Trong ví dụ thứ hai, Nam có một vé miễn phí. Nam dùng vé cho tuyến ~3~ (bến ~1 \rightarrow~ bến ~3~, tới lúc ~3~), rồi lên tuyến ~2~ rời bến ~3~ lúc ~4~, đi một chặng tới bến ~4~ và trả ~5~.