View as PDF

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

Authors:
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 friends! He will give out 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 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 of the 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 type of gift at all of the shops that he chooses will become the maximum price of the type of gift at those shops.

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

#### Constraints

1 5
2 15
3 20
4 60

All prices will be a positive integer no greater than .

#### Input Specification

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

lines of input follow. The line will contain space-separated integers; the integer represents the price of a gift of type from shop .

#### Output Specification

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

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

33

#### Explanation for Sample Output

Nathan can go to shops , , and . The prices for gifts of type , , and are , , and , respectively. The total cost of buying of each type of gift is therefore .