TLE '16 Contest 4 P5 - Buying Gifts

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 0.6s
Java 8 1.0s
Python 1.8s
Memory limit: 256M

Problem type
Disrupting the microwave shop industry and ripping consumers off since 2011.

Christmas is quickly approaching, so Nathan needs to buy gifts for each of his N friends! He will give out T possible types of gifts, and because he is in a very festive mood, each friend will receive each type of gift.

However, Nathan has not bought any of the gifts yet! He looks online and finds S gift shops; each shop sells exactly one of each type of gift at varying prices. Since Nathan wants to make a minimal number of trips, he will visit only N of the S shops.

Unfortunately for Nathan, the shopkeepers are not in a very festive mood. Before he visits any shop, the shopkeepers can work together to adjust the prices of their gifts. In particular, the price of the j^{th} type of gift at all of the N shops that he chooses will become the maximum price of the j^{th} type of gift at those N shops.

Nathan would like to know the minimum cost of buying gifts for all of his friends. Can you help him?


1 \leq N \leq S

1 \leq T

Subtask Points S T
1 5 S \le 1\,000 T = 1
2 15 S \le 1\,000 T = 2
3 20 S \le 15 T \le 5
4 60 S \le 30 T \le 5

All prices will be a positive integer no greater than 10^6.

Input Specification

The first line will contain three space-separated integers, S, N, and T.

S lines of input follow. The i^{th} line contains T space-separated integers; the j^{th} integer represents the price of a gift of type j from shop i.

Output Specification

Output a single integer, the minimum cost to buy gifts for all of Nathan's friends.

Sample Input

5 3 3
2 4 3
1 5 2
3 1 3
6 2 1
4 3 2

Sample Output


Explanation for Sample Output

Nathan can go to shops 1, 3, and 5. The prices for gifts of type 1, 2, and 3 are 4, 4, and 3, respectively. The total cost of buying 3 of each type of gift is therefore 33.


  • 0
    sunnylancoder  commented on Dec. 24, 2016, 1:13 p.m.

    Isn't it always possible for him to buy gifts for all his friends

    • 0
      ZQFMGB12  commented on Dec. 24, 2016, 3:28 p.m.

      Oops, printing -1 was possible in an older version of the problem. I've removed that part in the description.

    • 0
      d  commented on Dec. 24, 2016, 1:16 p.m.

      Yes, since N \le S.

      • 0
        jlsajfj  commented on Dec. 24, 2016, 3:19 p.m.

        Does that mean the program should never output -1

        • 0
          d  commented on Dec. 24, 2016, 3:25 p.m.

          It is always possible to select N out of the S shops. The program always outputs a positive integer.