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^\text{th} type of gift at all of the N shops that he chooses will become the maximum price of the j^\text{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 \le N \le S

1 \le 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^\text{th} line will contain T space-separated integers; the j^\text{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.


There are no comments at the moment.