Mỗi năm, hai thành phố láng giềng đều cử một đội gồm \(K\) thí sinh tham gia \(K\) nội dung thi khác nhau. Mỗi thí sinh tham gia tất cả các nội dung. Điểm của một đội ở một nội dung là điểm cao nhất mà một thí sinh trong đội đạt được ở nội dung đó. Tổng điểm của đội là tổng điểm của đội ở tất cả các nội dung. Chẳng hạn, nếu \(K=3\) và điểm của các thí sinh là \((4,5,3)\), \((7,3,6)\) và \((3,4,5)\), thì điểm của đội ở các nội dung là \((7,5,6)\) và tổng điểm bằng \(18\).

Mỗi thành phố có một tập thí sinh đủ điều kiện để cử đi thi. Hai thành phố bắt đầu tranh luận không chỉ về việc thành phố nào có đội mạnh nhất, mà còn về việc thành phố nào có đội mạnh thứ \(C\) tốt hơn, với một số nguyên \(C\). Ở đây, \(C=1\) tương ứng với đội mạnh nhất, \(C=2\) tương ứng với đội mạnh thứ hai, và cứ như vậy.

Bạn cần giúp một thành phố xác định tổng điểm dự kiến của đội mạnh thứ \(C\), xét tất cả các đội khác nhau gồm \(K\) người có thể lập từ những thí sinh đủ điều kiện của thành phố đó. Hai đội được xem là khác nhau nếu có ít nhất một thí sinh khác nhau.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên \(N\), \(K\), \(C\), trong đó \(N\) là tổng số thí sinh đủ điều kiện của thành phố, \(K\) là số thành viên trong đội (\(K\le N\)), và \(C\) là thứ hạng của đội cần tìm. Giá trị \(C\) không vượt quá số đội gồm \(K\) thành viên có thể lập được.

Mỗi dòng trong \(N\) dòng tiếp theo chứa \(K\) số nguyên không âm, là điểm dự kiến của một thí sinh ở \(K\) nội dung thi. Không điểm nào lớn hơn \(10^6\).

Dữ liệu ra

In trên một dòng tổng điểm của đội mạnh thứ \(C\).

Ràng buộc

\(1\le N\le 500\), \(1\le K\le 6\), \(1\le C\le 2000\), \(K\le N\). Giá trị \(C\) không vượt quá số đội có thể lập được. Mỗi điểm số nằm trong khoảng từ \(0\) đến \(10^6\).

Phân nhóm

1. Nhóm 1 (13 điểm): \(1\le N\le 500\), \(1\le K\le 2\), \(1\le C\le 2000\).
2. Nhóm 2 (31 điểm): \(1\le N\le 100\), \(1\le K\le 6\), \(1\le C\le 2000\).
3. Nhóm 3 (24 điểm): \(1\le N\le 500\), \(1\le K\le 6\), \(1\le C\le 2000\); không điểm nào lớn hơn \(10\).
4. Nhóm 4 (32 điểm): \(1\le N\le 500\), \(1\le K\le 6\), \(1\le C\le 2000\).

Ví dụ

5 4 4
7 0 4 9
3 0 8 4
1 1 3 7
5 1 3 4
4 2 2 9

24

Nguồn

Baltic Olympiad in Informatics 2019, ngày 2, Tartu, Estonia, 27/4–2/5/2019. Giấy phép CC BY-SA 4.0.