1310_D. Tourism_10211
Masha lives in a country with n cities numbered from 1 to n. She lives in the city number 1. 

There is a direct train route between each pair of distinct cities i and j, where i ≠ j. In total there are n(n-1) distinct routes. Every route has a cost, cost for route from i to j may be different from the cost of route from j to i.

Masha wants to start her journey in city 1, take exactly k routes from one city to another and as a result return to the city 1. Masha is really careful with money, so she wants the journey to be as cheap as possible. To do so Masha doesn't mind visiting a city multiple times or even taking the same route multiple times.

Masha doesn't want her journey to have odd cycles. Formally, if you can select visited by Masha city v, take odd number of routes used by Masha in her journey and return to the city v, such journey is considered unsuccessful.

Help Masha to find the cheapest (with minimal total cost of all taken routes) successful journey.

Input

First line of input had two integer numbers n,k (2 ≤ n ≤ 80; 2 ≤ k ≤ 10): number of cities in the country and number of routes in Masha's journey. It is guaranteed that k is even.

Next n lines hold route descriptions: j-th number in i-th line represents the cost of route from i to j if i ≠ j, and is 0 otherwise (there are no routes i → i). All route costs are integers from 0 to 10^8.

Output

Output a single integer — total cost of the cheapest Masha's successful journey.

Examples

Input


5 8
0 1 2 2 0
0 0 1 1 2
0 1 0 0 0
2 1 1 0 0
2 0 1 2 0


Output


2


Input


3 2
0 1 1
2 0 1
2 2 0


Output


3
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 85;
const long long maxk = 11;
const long long mod = 1e9 + 7;
const long long inf = 1e18;
mt19937 rng(time(0));
long long n, m, c[maxn][maxn], dp[maxk][maxn], ans;
vector<long long> a, b;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> m;
  for (long long i = 0; i < n; i++) {
    for (long long j = 0; j < n; j++) {
      cin >> c[i][j];
    }
  }
  ans = inf;
  for (long long o = 0; o < 5000; o++) {
    a.clear();
    b.clear();
    a.push_back(0);
    for (long long i = 1; i < n; i++) {
      if (rng() % 2)
        a.push_back(i);
      else
        b.push_back(i);
    }
    fill(dp[0] + 1, dp[0] + n, inf);
    for (long long i = 0; i < m / 2; i++) {
      fill(dp[i + 1], dp[i + 1] + n, inf);
      for (long long j : a) {
        for (long long k : b) {
          dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + c[j][k]);
        }
      }
      for (long long j : b) {
        for (long long k : a) {
          dp[i + 1][k] = min(dp[i + 1][k], dp[i + 1][j] + c[j][k]);
        }
      }
    }
    ans = min(ans, dp[m / 2][0]);
  }
  cout << ans;
  return 0;
}

5 8
0 1 2 2 0
0 0 1 1 2
0 1 0 0 0
2 1 1 0 0
2 0 1 2 0
 3 2
0 1 1
2 0 1
2 2 0
 4 2
0 49799607 47904756 8763425
57567044 0 80148623 61775195
3270902 91509738 0 8240512
54377373 35162721 35112487 0
 2 10
0 0
0 0
 2 10
0 3
0 0
 2 2
0 35949957
62693577 0
 3 10
0 8 3
3 0 1
9 2 0
 3 2
0 45391155 5299166
47959463 0 44352869
60236461 57436292 0
 4 4
0 94474339 70423020 9133992
51615028 0 51709029 6176813
91615211 81243650 0 1214040
55335766 55450190 86667677 0
 4 2
0 7524609 47904756 8763425
57567044 0 80148623 61775195
3270902 91509738 0 8240512
54377373 35162721 35112487 0
 2 2
0 35949957
92604921 0
 3 2
0 45391155 5299166
47959463 0 37700083
60236461 57436292 0
 4 4
0 94474339 70423020 9133992
62340782 0 51709029 6176813
91615211 81243650 0 1214040
55335766 55450190 86667677 0
 5 8
0 1 2 2 0
0 0 1 1 2
0 1 0 0 0
2 1 0 0 0
2 0 1 2 0
 3 2
0 1 1
2 1 1
2 2 0
 4 4
0 94474339 70423020 9133992
62340782 0 51709029 1625668
91615211 81243650 0 1214040
55335766 55450190 86667677 0
 5 8
0 1 2 2 0
0 0 2 1 2
0 1 0 0 0
2 1 0 0 0
2 0 1 2 0
 4 4
0 94474339 70423020 9133992
62340782 0 51709029 1625668
91615211 81243650 0 1214040
74819297 55450190 86667677 0
 3 2
1 26548208 5299166
47959463 0 24813021
92769107 57436292 0
 3 2
0 1 1
3 1 2
4 2 1
 3 2
2 39588791 9258200
47959463 0 24813021
92769107 57436292 0
 3 2
2 39588791 9258200
87379311 0 24813021
92769107 57436292 0
 3 2
2 39588791 12589613
87379311 0 24813021
92769107 57436292 0
 3 2
2 39588791 13110023
87379311 0 24813021
92769107 46997844 0
 4 2
0 7524609 47904756 8763425
57567044 0 80148623 61775195
3270902 91509738 0 8240512
54377373 38665367 35112487 0
 3 2
0 26548208 5299166
47959463 0 37700083
60236461 57436292 0
 3 2
0 1 1
2 1 2
2 2 0
 4 2
0 11323753 47904756 8763425
57567044 0 80148623 61775195
3270902 91509738 0 8240512
54377373 38665367 35112487 0
 3 2
1 26548208 5299166
47959463 0 37700083
60236461 57436292 0
 5 8
0 1 2 2 0
0 0 2 1 2
0 1 0 0 0
4 1 0 0 0
2 0 1 2 0
 3 2
0 1 1
3 1 2
2 2 0
 3 2
1 26548208 5299166
47959463 0 24813021
60236461 57436292 0
 5 8
0 1 2 2 0
0 0 2 1 2
0 1 0 0 0
4 1 0 0 0
2 0 1 2 1
 3 2
0 1 1
3 1 2
2 2 1
 5 8
0 1 2 2 0
0 0 2 1 0
0 1 0 0 0
4 1 0 0 0
2 0 1 2 1
 3 2
2 26548208 5299166
47959463 0 24813021
92769107 57436292 0
 5 8
0 1 2 2 0
0 0 2 1 0
0 1 0 0 -1
4 1 0 0 0
2 0 1 2 1
 3 2
0 1 1
3 1 2
4 4 1
 3 2
2 26548208 9258200
47959463 0 24813021
92769107 57436292 0
 5 8
0 1 2 2 0
0 0 2 1 0
0 1 0 0 -1
4 1 0 0 0
2 0 2 2 1
 3 2
0 1 0
3 1 2
4 4 1
 5 8
0 1 2 2 0
0 0 2 1 0
0 1 0 0 -1
4 1 0 0 0
2 0 2 4 1
 3 2
0 1 0
3 1 2
1 4 1
 5 8
0 1 2 2 0
1 0 2 1 0
0 1 0 0 -1
4 1 0 0 0
2 0 2 4 1
 3 2
0 1 1
3 1 2
1 4 1
 5 8
0 2 2 2 0
1 0 2 1 0
0 1 0 0 -1
4 1 0 0 0
2 0 2 4 1
 3 2
0 1 1
3 1 2
1 3 1
 3 2
2 39588791 12589613
87379311 0 24813021
92769107 28336372 0
 5 8
0 2 2 2 0
1 0 2 1 0
0 1 0 0 -1
4 1 0 0 0
2 0 2 8 1
 3 2
0 2 1
3 1 2
1 4 1
 3 2
2 39588791 12589613
87379311 0 24813021
92769107 46997844 0
 5 8
0 2 1 2 0
1 0 2 1 0
0 1 0 0 -1
4 1 0 0 0
2 0 2 8 1
 3 2
0 2 1
3 1 2
1 6 1
 5 8
0 2 1 2 0
1 0 2 1 0
0 1 0 0 -1
4 2 0 0 0
2 0 2 8 1
 3 2
0 0 1
3 1 2
1 6 1
 3 2
2 69323548 13110023
87379311 0 24813021
92769107 46997844 0
 3 2
0 -1 1
3 1 2
1 6 1

2
 3
 51175658
 0
 15
 98643534
 23
 65535627
 126096761
 51175658 128554878 65535627 126096761 1 3 121545616 2 141029147 74507671 4 87548254 102027307 105358720 105879130 51175658 65535627 3 51175658 65535627 2 3 65535627 2 3 1 74507671 1 4 74507671 1 4 1 1 2 2 2 2 105358720 2 2 105358720 1 2 1 2 105879130 2