Under construction

Still being built. Things may change

I Am a Great Superstar K

Time limit1sMemory limit128 MB

Summary
Given N contestants' scores in M genres (each genre's scores listed sorted), pick K contestant-genre assignments (one genre per chosen contestant) maximizing total score, requiring a min-cost/max-flow or matroid intersection style greedy insight.
Level

Hard8 of 10

Topics
Greedy, Graph, Dynamic programming
Solved
No attempts yet

Problem

Sanggeun directs the singing competition "I Am a Great Superstar K". He wants to choose finalists as follows.

There are N participants in the preliminary round, and each participant auditioned in M different genres. The judges assigned a real-valued score for every participant in every genre.

Exactly K participants can advance to the final round. Each finalist may sing exactly one genre in the final, and Sanggeun chooses that genre. A participant cannot sing multiple genres, but multiple participants may sing the same genre.

Given every participant's score in every genre, choose the finalists and their genres so that the total score is as large as possible.

Input

The first line contains N, M, and K. (1 <= M <= 100, 1 <= K <= N <= 100)

Each of the next M lines gives the participants' scores for one genre. A line contains N pairs (i, s), where i is a participant number and s is that participant's score in the genre. The pairs are given in non-increasing order of score. Participant numbers are from 1 to N.

Every participant appears exactly once on each of these lines.

Output

Print the maximum possible total score of the finalists, rounded to one digit after the decimal point.

Examples2

  1. Example 1

    Input
    3 2 2
2 3.0 1 0.2 3 0.1
3 1.0 2 0.5 1 0.2
    Expected output
    4.0

  2. Example 2

    Input
    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
    Expected output
    15.0