Buôn Bán Giữa Các Hành Tinh

Một thương nhân muốn kiếm lời bằng cách mua hàng tại một hành tinh rồi bay sang một hành tinh khác để bán toàn bộ. Việc mua và bán chỉ diễn ra duy nhất một lần.

Hệ có $n$ hành tinh, trên mỗi hành tinh đều bán $m$ loại hàng. Với mỗi hành tinh $i$ và mỗi loại hàng $j$ ta biết:

• $a_{ij}$ — giá mua một đơn vị loại $j$ trên hành tinh $i$;
• $b_{ij}$ — giá bán một đơn vị loại $j$ trên hành tinh $i$;
• $c_{ij}$ — số đơn vị loại $j$ còn lại trên hành tinh $i$.

Khi đặt chân lên hành tinh mua, thương nhân không được mua quá $c_{ij}$ đơn vị mỗi loại; còn khi sang hành tinh bán thì có thể bán không giới hạn số lượng cho mỗi loại. Khoang chứa của tàu chỉ chở được tối đa $k$ đơn vị hàng (tổng tất cả các loại).

Hãy xác định lợi nhuận lớn nhất có thể thu được. Lưu ý: thương nhân có quyền không mua gì cả, khi đó lợi nhuận bằng $0$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• Tiếp theo là $n$ khối mô tả các hành tinh. Khối thứ $i$ gồm:
  • Một dòng chứa tên hành tinh (chuỗi từ $1$ đến $10$ chữ cái Latinh, chữ cái đầu viết hoa, các chữ còn lại viết thường).
  • $m$ dòng tiếp, dòng thứ $j$ chứa ba số $a_{ij}$, $b_{ij}$, $c_{ij}$.

Tên các hành tinh đôi một khác nhau.

Dữ liệu ra

In ra một số nguyên duy nhất — lợi nhuận lớn nhất.

Ràng buộc

• $2\le n\le 10$
• $1\le m,k\le 100$
• $1\le b_{ij}<a_{ij}\le 1000$
• $0\le c_{ij}\le 100$

Ví dụ