题目描述

有一支队伍共 $n$ 个人准备参加 $m$ 类比赛。对于每一类比赛，每个人都有对这类比赛知识的积累程度（用一个一位小数表示）。作为教练，你需要派出 $k$ 名选手参赛。

已知一个人最多只能参加一类比赛，多个人可以同时参加同一类比赛，可以有选手不参赛。请你安排 $k$ 名选手参加比赛，使得所有这 $k$ 名选手知识积累程度之和最大。

输入格式

输入第一行三个整数 $n,m,k$，分别表示总人数，比赛种类数，实际派出选手数。

接下来的 $m$ 行，描述 $m$ 类比赛。每行 $n$ 个数对 $(i,s)$，表示编号为 $i$ 的选手对这类比赛的知识积累程度为 $s$。按照 $s$ 递减的顺序给出这 $n$ 个数对，每名选手会且仅会出现一次。

输出格式

输出一行一个实数，表示最大的知识积累程度总和。保留一位小数。

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

提示

样例 1 解释

对于这个样例，我们分别派 $2$ 号选手参加第一类竞赛，$3$ 好选手参加第二类竞赛，这样使得总和最大为 $3.0+1.0=4.0$。

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le m\le 100$，$1\le k\le n\le 100$。

说明

题目译自 COCI2010-2011 CONTEST #3 T3 EKIPA。