Every year, Ohrid is the host of the Ohrid Choir festival - a popular festival that attracts choirs and singing formations from different countries. Just like the organizers of JBOI, the organizers of the Ohrid Choir Festival 2012 have chosen several very pretty girls to serve as guides during the festival. The guides are responsible for helping the participants find their way around Ohrid.

As you probably already know, it is good practice for all participants from a certain country to have one unique guide - so they can walk and swim together. Marko, one of the organizers of the festival, however, wasn't that smart - he made a big mess and told each participant of the Ohrid Choir Festival a random guide's name. Now, your job is to help Marko determine the minimum number of participants that he should talk to (and tell them they have a new guide) in order to fix the problem: make each guide responsible for participants from at most one country, and make sure all participants from one country have the same guide. If there are more guides than participating countries, some guides can end up not being responsible for anyone.

Input

The first line of input contains two integers N (1 ≤ N ≤ 100) and M (1 ≤ M ≤ 15 and M ≤ N), where N is the number of guides and M is the number of participating countries at the Ohrid Choir Festival 2012. The following N lines describe the number of participants for which each guide is responsible for: every line contains M integers Xij (0 ≤ Xij ≤ 10), where Xij is the number of participants of the j-th country that the i-th guide is responsible for (the first row contains X₁₁, X₁₂, X₁₃, ..., X_1M, the second row contains X₂₁, X₂₂, X₂₃, ..., X_2M, etc). There are at least 2 participants from each country at this year's Ohrid Choir Festival.

In test cases worth at least 20% of the full score, M will be an integer smaller than 5 (1 ≤ M < 5 and M ≤ N).

Output

Your program should output exactly one integer - the required minimum number of participants that Marko should talk to.

Constraints

Time limit: 1 second
Memory limit: 64 megabytes

Examples

input
3 2
4 9
1 0
2 0

output
5

Explanation of test example 1: Marko should talk to 5 participants. After the reorganization, guide number 1 is responsible for 9 participants (from country number 2), and guide number 3 is responsible for 4+1+2=7 participants (from country number 1).