In a galaxy far, far away, a programming contest is taking place. Your task is to choose the participants!

\(N\) students have applied, and each one of them has some knowledge in each of \(M\) different categories. Knowledge can be represented as a real number. You can send at most \(K\) students to the contest, but no student can compete in more than one category. Multiple students can compete in a single category.

For each student, their knowledge of each category is given. Choose participants for the contest and the categories they will compete in, so that the sum of knowledge is maximal.

The first line of input contains integers \(N\), \(M\) and \(K\) (\(1 \le M \le 100\), \(1 \le K \le N \le 100\)).

Each of the next \(M\) lines describes the knowledge for one category. In each line there are \(N\) pairs \((i, s)\), where \(i\) is the index of the student and \(s\) is a positive real number representing their knowledge of the corresponding category (\(0 \le s \le 10\)). Pairs are given in order of decreasing knowledge. Students are numbered from \(1\) to \(N\). In each line, every student appears exactly once.

The first and only output line should contain the maximum sum of knowledge the chosen students can have, with exactly one digit in the decimal part.

First sample description: There are two categories. In the first category, the best student is number \(2\), with knowledge \(3.0\). He is followed by student \(1\) (knowledge \(0.2\)), and then student \(3\) (knowledge \(0.1\)). The best solution is to choose students \(2\) and \(3\), in categories \(1\) and \(2\) respectively.

riseoj 작성

출처 COCI 2010/2011 Contest 3