Thuê bạn giải bài

Bạn cần giải $m$ bài tập và có thể nhờ $n$ người bạn làm hộ.

Người bạn thứ $i$ lấy $x_i$ đồng để giải tất cả những bài mà anh ta biết làm. Ngoài ra anh ta chỉ chịu ngồi viết code nếu máy tính của bạn được 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 chưa nối màn hình nào.

Các màn hình được dùng chung, nên nếu bạn thuê một nhóm người bạn thì số màn hình phải mua đúng bằng giá trị $k_i$ lớn nhất trong nhóm đó.

Hãy tìm tổng số tiền nhỏ nhất để cả $m$ bài đề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$.
• $2n$ dòng tiếp theo mô tả $n$ 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 yêu cầu, số màn hình yêu cầu và số bài anh ta giải được.
  • Dòng thứ hai chứa $m_i$ số nguyên phân biệt — chỉ số các bài anh ta giải được.

Các bài tập được đánh số từ $1$ đến $m$.

Dữ liệu ra

Một số nguyên duy nhất là tổng chi phí nhỏ nhất, hoặc $-1$ nếu không thể giải hết $m$ bài.

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$
• Kết quả có thể vượt quá phạm vi số nguyên 32 bit.

Ví dụ