Digits in optimal order P46547

Given two natural numbers m and n, you must construct a number x using the digits {1, …, n} (exactly one of each) such that no (non-empty) prefix of x is a multiple of m. For example, with m=3 and n=4, x=2314 is not a valid order, because 231 is a multiple of 3. In contrast, x=4312 is a valid order, because neither 4, nor 43, nor 431, nor 4312 are multiples of 3.

Moreover, you have a matrix M[1..n][1..n] such that M[i][j] contains the prize that is obtained if digit j is placed immediately to the right of digit i. Maximize the total sum of the prizes.

Input

The input consists of several cases. Each case starts with m and n, followed by M: n rows, each with n natural numbers between 1 and 10⁶, except for the diagonal, that is filled with zeros. You can assume that 3 ≤ m ≤ 1000 and 2 ≤ n ≤ 9.

Output

For each case, print the maximum possible prize. If no x can be constructed, print 0.