Sinh kịch bản

Một bộ phim truyền hình có $n$ nhân vật nam và $n$ nhân vật nữ, đều đang độc thân. Khảo sát khán giả chỉ ra $k$ cặp đôi được yêu thích, cặp thứ $i$ gồm chàng trai $h_i$, cô gái $w_i$, và nếu họ cưới nhau thì khán giả hài lòng thêm $r_i$ điểm. Mọi cặp đôi khác không nằm trong danh sách sẽ không được biên kịch xét đến.

Kịch bản được phép tổ chức một số đám cưới bất kỳ trong $k$ cặp trên, hoặc không tổ chức đám cưới nào. Một tập con các đám cưới được gọi là chấp nhận được nếu mỗi chàng trai và mỗi cô gái tham gia nhiều nhất một đám cưới trong tập đó. Giá trị của một tập chấp nhận được là tổng số điểm hài lòng của các đám cưới trong tập.

Số tập chấp nhận được là hữu hạn. Hãy sắp xếp tất cả các tập chấp nhận được theo thứ tự giá trị không giảm và cho biết giá trị của tập thứ $t$ trong danh sách đó. Như vậy $t=1$ ứng với tập rỗng (không đám cưới nào), $t=2$ ứng với đám cưới đơn lẻ có điểm nhỏ nhất, và cứ thế tiếp tục.

Hai tập chấp nhận được khác nhau vẫn được tính là hai phần tử khác nhau của danh sách kể cả khi chúng có cùng giá trị.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $k$, $t$.
• $k$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $h_i$, $w_i$, $r_i$ mô tả một cặp đôi được khán giả yêu thích.

Dữ liệu ra

Một số nguyên duy nhất: giá trị của tập chấp nhận được đứng thứ $t$ khi sắp xếp theo giá trị không giảm.

Ràng buộc

• $1\le n\le 20$
• $1\le k\le min(100,n^2)$
• $1\le t\le 2·{10}^5$
• $1\le h_i,w_i\le n$
• $1\le r_i\le 1000$
• Mỗi cặp $(h,w)$ xuất hiện trong nhiều nhất một dòng.
• Dữ liệu đảm bảo $t$ không vượt quá tổng số tập chấp nhận được.

Ví dụ