Chicken Chicken Chicken

Time limit1sMemory limit128 MB

Summary
Given N members' preference scores for M chicken kinds, choose at most 3 kinds to maximize the sum over members of their highest preference among the chosen kinds.
Level

Medium5 of 10

Topics
Brute force, Implementation, Array
Solved
No attempts yet

Problem

N members of Gori want to order chicken.

There are M kinds of chicken in total, and each member has a preference for each kind of chicken. A person's satisfaction is determined by the largest preference among the chicken they ordered. Jinsu wants to order chicken so that the sum of the members' satisfaction is maximized.

Since ordering more kinds of chicken also takes longer to fry, he wants to order at most three kinds of chicken.

Help Jinsu find the maximum possible sum of satisfaction.

Input

The first line gives the number of Gori members N (1 ≤ N ≤ 30) and the number of chicken kinds M (3 ≤ M ≤ 30).

The next N lines give each member's chicken preferences.

The i+1-th line gives the preferences of the i-th member, a**i,1, a**i,2, ..., a**i,M (1 ≤ a**i,j ≤ 9).

Output

On the first line, print the maximum sum of the Gori members' satisfaction.

Examples2

  1. Example 1

    Input
    3 5
1 2 3 4 5
5 4 3 2 1
1 2 3 2 1
    Expected output
    13

  2. Example 2

    Input
    4 6
1 2 3 4 5 6
6 5 4 3 2 1
3 2 7 9 2 5
4 5 6 3 2 1
    Expected output
    25