Description

A team of $n$ people is going to take part in $m$ types of contests. For each type of contest, each person has a level of knowledge accumulation for that contest (given as a decimal with one digit after the point). As the coach, you need to send $k$ contestants to compete.

It is known that one person can take part in at most one type of contest. Multiple people may take part in the same type of contest, and some people may also not compete. Please arrange $k$ contestants to take part in contests so that the sum of the knowledge accumulation levels of these $k$ contestants is maximized.

Input Format

The first line contains three integers $n,m,k$, representing the total number of people, the number of contest types, and the number of contestants actually sent.

The next $m$ lines describe the $m$ types of contests. Each line contains $n$ pairs $(i,s)$, meaning that contestant with index $i$ has knowledge accumulation level $s$ for this contest type. These $n$ pairs are given in decreasing order of $s$, and each contestant appears exactly once.

Output Format

Output one real number in a single line, representing the maximum total sum of knowledge accumulation levels. Keep one digit after the decimal point.

3 2 2
2 3.0 1 0.2 3 0.1
3 1.0 2 0.5 1 0.2

4.0

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

15.0

Hint

Explanation for Sample 1

For this sample, we send contestant $2$ to the first contest type and contestant $3$ to the second contest type. This makes the maximum total $3.0+1.0=4.0$.

Constraints

For $100\%$ of the testdata, it is guaranteed that $1\le m\le 100$, $1\le k\le n\le 100$.

Note

This problem is translated from COCI2010-2011 CONTEST #3 T3 EKIPA。

Translated by ChatGPT 5