Mô tả

Chương trình thi chung kết Tin học bao gồm m lĩnh vực. Có n người đăng ký dự thi. Ở mỗi lĩnh vực, mỗi người có một tiềm năng riêng được xác định bằng một số thực. Đội dự thi bao gồm không quá k người, mỗi người chỉ được dự thi ở một lĩnh vực. Tuy vậy có thể có nhiều người cùng thi một lĩnh vực.

Cho n, m, k và tiềm năng của mỗi người trong từng lĩnh vực (1 ≤ m ≤ 100, 1 ≤ k ≤ n ≤ 100). Những người đăng ký được đánh số từ 1 đến n. Hãy xác định tổng tiềm năng lớn nhất có thể có khi thành lập đội dự thi.

Dữ liệu vào

Dòng đầu tiên chứa 3 số nguyên n, m và k. Dòng thứ j trong m dòng sau chứa n cặp số (i, s), trong đó s là tiềm năng của người thứ i trong chuyên mục j (s là số thực, 1 ≤ s ≤ 10), các cặp số được đưa ra theo thứ tự giảm dần của s.

Dữ liệu ra

Đưa ra một số thực với độ chính xác một chữ số sau dấu phảy thập phân là tổng tiềm năng lớn nhất có thể có của đội dự thi.

Ví dụ dữ liệu vào3 2 2 2 3.0 1 0.2 3 0.1 3 1.0 2 0.5 1 0.2

Ví dụ dữ liệu ra4.0

Gợi ý

Ví dụ dữ liệu vào:

4 4 3 4 5.0 2 4.0 3 2.0 1 1.0 2 2.0 3 1.0 1 0.5 4 0.3 4 6.0 3 5.0 2 2.0 1 0.0 1 4.0 2 3.0 4 0.6 3 0.3

Ví dụ dữ liệu ra:

15.0