Little Peter owns ~N~ glasses of infinite volume, and each glass contains some water. Peter wants to drink all the water, but he doesn’t want to drink from more th an ~K~ glasses. What Mislav can do with the glasses is pour the total volume of water from one glass to another.

Unfortunately, it matters to Peter what glass he picks, because not all glasses are equally distant to him. More precisely, the amount of effort it takes to pour water from glass labeled with i to glass labeled ~j~ is denot e d with C_ij..

Help Peter and find the order of pouring the water from one glass to another such that the sum of effort is minimal.

INPUT

The first line of input contain s integers ~N, K (1 \leq K \leq N \leq 20)~. The following ~N~ lines contains ~N~ integers ~C_{ij} (0 \leq C_{ij} \leq 10^5)~. The ith row and jth column contains value ~C_{ij}~. . It will h old that each ~C_{ii}~. is equal to 0.

OUTPUT

Output the minimal effort needed for Mislav to achieve his goal.

Samples

Input 1

3 3
0 1 1
1 0 1
1 1 0

Output 1

0

Input 2

3 2
0 1 1
1 0 1
1 1 0

Output 2

1

Input 3

5 2
0 5 4 3 2
7 0 4 4 4
3 3 0 1 2
4 3 1 0 5
4 5 5 5 0

Output 3

5

Clarification of the first test case: Mislav doesn’t need to pour water in order to drink from at most 3 glasses.

Clarification of the second test case: Mislav must pour the water from precisely one (doesn’t matter which) glass into any other glass in order to be left with only two glasses with water.

Clarification of the third test case: In order for Mislav to achieve the minimal solution of 5, he can pour water from glass 4 to 3 (effort 1), then ~3 \geq 5~ (effort 2), and finally, ~1 \geq 5~ (effort 2). In total, ~1 + 2 + 2 = 5~ amount of effort.