Một công ty có \(n\) nhân viên được chia thành \(m\) nhóm. Với mỗi nhân viên, giám đốc công ty biết nhóm và lương của nhân viên đó. Giám đốc muốn lựa chọn trưởng nhóm cho từng nhóm thỏa mãn điều kiện:

• Mỗi nhóm lựa chọn đúng một người và phân công người đó làm trưởng nhóm một nhóm nào đó (thậm chí chính nhóm hiện tại);
• Mỗi nhóm có đúng một trưởng nhóm;
• Trong mỗi nhóm, tổng số tiền lương của những người còn lại trong nhóm không được nhiều hơn tiền lương của người trưởng nhóm.

Yêu cầu: Tìm cách lựa chọn các trưởng nhóm và phân vào các nhóm thỏa mãn yêu cầu trên sao cho tổng tiền lương của các trưởng nhóm là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên \(m, n\) (\(m \le \min(15, n)\)).
• Tiếp theo là \(m\) dòng, mỗi dòng mô tả một nhóm có định dạng: số đầu tiên là số \(s\) (số người trong nhóm đó), tiếp theo là \(s\) số nguyên là lương của từng người trong nhóm. Các số nguyên dương không vượt quá \(10^9\).

Output

• Gồm một dòng duy nhất chứa một số nguyên là tổng tiền lương nhỏ nhất của các trưởng nhóm. Nếu không có phương án thỏa mãn, ghi \(-1\).

Example

3 7
3 1 2 3
2 3 2
3 1 2 2

8

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 15\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 50\).

Nguồn: 3D'21