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;
}
