Xây dựng đội bóng

Có $n$ người ứng tuyển vào một câu lạc bộ thể thao. Câu lạc bộ cần chọn đúng $p$ cầu thủ thi đấu tại $p$ vị trí khác nhau (mỗi vị trí đúng một người) và đúng $k$ cổ động viên. Mỗi người chỉ có thể đảm nhận tối đa một vai trò (hoặc cầu thủ tại một vị trí, hoặc cổ động viên).

Với người thứ $i$:

• $a_i$ là sức mạnh người đó đóng góp nếu được chọn làm cổ động viên.
• $s_{i,j}$ là sức mạnh người đó đóng góp nếu được chọn làm cầu thủ thi đấu tại vị trí $j$.

Tổng sức mạnh của câu lạc bộ là tổng tất cả các đóng góp của những người được chọn. Hãy chọn $p$ cầu thủ (một người cho mỗi vị trí) và $k$ cổ động viên sao cho tổng sức mạnh này lớn nhất.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $p$, $k$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• Trong $n$ dòng tiếp theo, dòng thứ $i$ chứa $p$ số nguyên $s_{i,1},s_{i,2},\dots ,s_{i,p}$.

Dữ liệu ra

• Một số nguyên duy nhất là tổng sức mạnh lớn nhất có thể của câu lạc bộ.

Ràng buộc

• $2\le n\le {10}^5$
• $1\le p\le 7$
• $1\le k$ và $p+k\le n$
• $1\le a_i\le {10}^9$
• $1\le s_{i,j}\le {10}^9$

Ví dụ