13941번 - Kronican 다국어

Little Mislav owns N glasses of infinite volume, and each glass contains some water. Mislav wants to drink all the water, but he doesn’t want to drink from more than 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 Mislav 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 denoted with C_ij.

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

The first line of input contains integers N, K (1 ≤ K ≤ N ≤ 20).

The following N lines contains N integers C_ij (0 ≤ C_ij ≤ 10⁵ ). The ith row and jth column contains value C_ij . It will hold that each Cii is equal to 0. 

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

 ​Mislav doesn’t need to pour water in order to drink from at most 3 glasses.