To read the problem statement in English, choose the language using the flag on the navigation bar.

Center Supermeowket là hệ thống siêu thị lớn nhất trên hành tinh mèo. Hiện tại, siêu thị đang tiến hành chương trình khuyến mãi đặc biệt với thể lệ như sau:

Có ~n~ gói khuyến mãi, mỗi gói khuyến mãi gồm ~m~ phần quà. Phần quà thứ ~j~ của gói khuyến mãi thứ ~i~ có giá trị là ~A_{i, j}~. Các phần quà trong cùng một gói khuyến mãi sẽ có giá trị không giảm (phần quà sau sẽ có giá trị lớn hơn hoặc bằng phần quà trước).

Khách hàng có thể đổi quà khuyến mãi bằng điểm khách hàng thân thiết (KHTT). Cụ thể, với mỗi gói khuyến mãi, khách hàng có thể đổi ~x~ điểm (với ~0 \le x \le m~) để nhận ~x~ món quà đầu tiên của gói. Lưu ý rằng, chỉ có thể đổi điểm tối đa một lần với mỗi gói. Và hiển nhiên, tổng số điểm dùng để đổi quà không thể lớn hơn số điểm KHTT hiện có.

Neko, một khách hàng lâu năm của Center Supermeowket, hiện tại đang có ~k~ điểm KHTT. Cậu muốn biết rằng, với cách đổi quà tối ưu thì tổng giá trị tối đa của các phần quà mà cậu nhận được là bao nhiêu.

Input

Dòng đầu tiên gồm ba số nguyên ~n~, ~m~, ~k~ (~1 \le n \le 10^5~, ~1 \le m \le 10~, ~1 \le k \le n \cdot m~), lần lượt là số gói khuyến mãi, số phần quà trong mỗi gói và số điểm KHTT hiện có.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ~m~ số nguyên dương ~A_{i,1}, A_{i,2}, \ldots, A_{i,m}~ (~1 \le A_{i,1} \le A_{i,2} \le \ldots \le A_{i,m} \le 10^9~), lần lượt là giá trị của các phần quà trong gói khuyến mãi thứ ~i~.

Output

In ra một số nguyên duy nhất là tổng giá trị các phần quà tối đa có thể đổi được.

Scoring

• Subtask 1, tương ứng với ~30~ điểm, có ~n \le 15~ và ~m = 2~

• Subtask 2, tương ứng với ~45~ điểm, có ~n \le 300~

• Subtask 3, tương ứng với ~75~ điểm, không có giới hạn gì thêm

Tổng cộng bài toán này có ~150~ điểm.

Sample Input 1

3 2 3
1 3
2 9
7 8

Sample Output 1

18

Notes

Neko sẽ đổi 2 phần quà ở gói thứ hai, và 1 phần quà ở gói thứ ba. Tổng giá trị quà nhận được là ~2 + 9 + 7 = 18~.