在一个遥远的星系中，正在举办一场程序设计竞赛。你的任务是选拔参赛队员！

有 $N$ 名学生报名，每名学生在 $M$ 个不同的方向上都有一定的知识水平。知识水平可以用一个实数表示。你最多可以派出 $K$ 名学生参加比赛，但任何学生都不能参加超过一个方向的比赛。多名学生可以参加同一个方向的比赛。

已知每名学生在每个方向上的知识水平。

请选择参赛的学生以及他们参加的方向，使得所选学生的知识水平之和最大。

输入格式

输入的第一行包含整数 $N$，$M$ 和 $K$（$1 \le M \le 100$，$1 \le K \le N \le 100$）。

接下来的 $M$ 行，每行描述一个方向的知识水平。

在每行中，有 $N$ 对 $(i, s)$，其中 $i$ 是学生的编号，$s$ 是一个正实数，表示该学生在对应方向上的知识水平（$0 \le s \le 10$）。这些对按照知识水平降序给出。学生编号从 $1$ 到 $N$。

在每行中，每名学生都会恰好出现一次。

输出格式

输出的第一行，也是唯一的一行，应该包含所选学生的最大知识水平之和，保留恰好一位小数。

样例

输入 1

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

输出 1

4.0

输入 2

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

输出 2

15.0

说明

样例 1 说明

共有两个方向。在第一个方向中，最优秀的学生是 2 号，知识水平为 3.0。其次是 1 号学生，知识水平为 0.2，然后是 3 号学生，知识水平为 0.1。

最佳方案是分别选择 2 号和 3 号学生参加第 1 和第 2 个方向。