Gena tinh ranh

Gena muốn giải hết $m$ bài toán trong một kỳ thi, nhưng các bài quá khó nên cậu nhờ $n$ người bạn giải giúp.

Với mỗi người bạn, Gena biết người đó có thể giải được những bài nào. Tuy nhiên, không ai giúp miễn phí:

• Người bạn thứ $i$ đòi $x_i$ đồng để giải toàn bộ các bài mà người đó biết cách giải.
• Ngoài ra, người bạn thứ $i$ chỉ chịu viết code cho Gena nếu máy tính của Gena được kết nối với ít nhất $k_i$ màn hình.

Mỗi màn hình có giá $b$ đồng. Ban đầu máy tính của Gena chưa có màn hình nào. Số màn hình cần mua là số màn hình đủ để thỏa mãn tất cả những người bạn được Gena thuê: nếu Gena thuê một nhóm bạn thì cậu phải có số màn hình bằng giá trị $k_i$ lớn nhất trong nhóm đó.

Tổng chi phí Gena phải trả bằng tổng số tiền $x_i$ của những người bạn được thuê, cộng với chi phí mua màn hình.

Hãy tìm số tiền nhỏ nhất Gena cần chi để cả $m$ bài toán đều được giải, hoặc cho biết điều đó là không thể.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $b$: số người bạn, số bài toán và giá một màn hình.
• Tiếp theo là $2n$ dòng mô tả các người bạn. Với người bạn thứ $i$:
  • Dòng thứ nhất chứa ba số nguyên $x_i$, $k_i$, $m_i$: số tiền đòi hỏi, số màn hình yêu cầu, và số bài người đó giải được.
  • Dòng thứ hai chứa $m_i$ số nguyên phân biệt: chỉ số các bài mà người bạn thứ $i$ giải được (đánh số từ $1$ đến $m$).

Dữ liệu ra

In ra một số nguyên: số tiền nhỏ nhất Gena cần chi để giải hết $m$ bài, hoặc $-1$ nếu không thể giải hết.

Ràng buộc

• $1\le n\le 100$
• $1\le m\le 20$
• $1\le b\le {10}^9$
• $1\le x_i\le {10}^9$
• $1\le k_i\le {10}^9$
• $1\le m_i\le m$

Ví dụ