#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
const int size1 = 4e5;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  static int g[81][81], g1[81][81];
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cin >> g[i][j];
      g1[j][i] = g[i][j];
    }
  }
  const int c = 81;
  vector<vector<vector<pair<int, int>>>> v(c);
  for (int i = 0; i < 81; ++i) {
    v[i].resize(c);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        if (k != i && k != j) {
          v[i][j].push_back({g[i][k] + g[k][j], k});
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      sort(v[i][j].begin(), v[i][j].end());
    }
  }
  if (k == 2) {
    cout << v[1][1][0].first;
    return 0;
  }
  const int INF = 2e9;
  if (k == 4) {
    int ans = INF;
    int cur = 0;
    for (int i1 = 1; i1 <= n; ++i1) {
      cur = 0;
      bool res = true;
      if (v[1][i1].empty()) {
        res = false;
      }
      if (v[i1][1].empty()) {
        res = false;
      }
      for (int i = 0; i < v[1][i1].size(); ++i) {
        if (v[1][i1][i].second != 1 && v[1][i1][i].second != i1) {
          cur += v[1][i1][i].first;
          break;
        }
        if (1 + i == v[1][i1].size()) {
          res = false;
        }
      }
      for (int i = 0; i < v[i1][1].size(); ++i) {
        if (v[i1][1][i].second != 1 && v[i1][1][i].second != i1) {
          cur += v[i1][1][i].first;
          break;
        }
        if (1 + i == v[i1][1].size()) {
          res = false;
        }
      }
      if (res) ans = min(ans, cur);
    }
    cout << ans;
    return 0;
  }
  if (k == 6) {
    int ans = INF;
    int cur = 0;
    for (int i1 = 1; i1 <= n; ++i1) {
      for (int i2 = 1; i2 <= n; ++i2) {
        cur = 0;
        bool res = true;
        if (v[1][i1].empty()) {
          res = false;
        }
        if (v[i1][i2].empty()) {
          res = false;
        }
        if (v[i2][1].empty()) {
          res = false;
        }
        for (int i = 0; i < v[1][i1].size(); ++i) {
          if (v[1][i1][i].second != 1 && v[1][i1][i].second != i1 &&
              v[1][i1][i].second != i2) {
            cur += v[1][i1][i].first;
            break;
          }
          if (1 + i == v[1][i1].size()) {
            res = false;
          }
        }
        for (int i = 0; i < v[i1][i2].size(); ++i) {
          if (v[i1][i2][i].second != 1 && v[i1][i2][i].second != i1 &&
              v[i1][i2][i].second != i2) {
            cur += v[i1][i2][i].first;
            break;
          }
          if (1 + i == v[i1][i2].size()) {
            res = false;
          }
        }
        for (int i = 0; i < v[i2][1].size(); ++i) {
          if (v[i2][1][i].second != 1 && v[i2][1][i].second != i1 &&
              v[i2][1][i].second != i2) {
            cur += v[i2][1][i].first;
            break;
          }
          if (1 + i == v[i2][1].size()) {
            res = false;
          }
        }
        if (res) ans = min(ans, cur);
      }
    }
    cout << ans;
    return 0;
  }
  if (k == 8) {
    int ans = INF;
    int cur = 0;
    for (int i1 = 1; i1 <= n; ++i1) {
      for (int i2 = 1; i2 <= n; ++i2) {
        for (int i3 = 1; i3 <= n; ++i3) {
          cur = 0;
          bool res = true;
          if (v[1][i1].empty()) {
            res = false;
          }
          if (v[i1][i2].empty()) {
            res = false;
          }
          if (v[i2][i3].empty()) {
            res = false;
          }
          if (v[i3][1].empty()) {
            res = false;
          }
          for (int i = 0; i < v[1][i1].size(); ++i) {
            if (v[1][i1][i].second != 1 && v[1][i1][i].second != i1 &&
                v[1][i1][i].second != i2 && v[1][i1][i].second != i3) {
              cur += v[1][i1][i].first;
              break;
            }
            if (1 + i == v[1][i1].size()) {
              res = false;
            }
          }
          for (int i = 0; i < v[i1][i2].size(); ++i) {
            if (v[i1][i2][i].second != 1 && v[i1][i2][i].second != i1 &&
                v[i1][i2][i].second != i2 && v[i1][i2][i].second != i3) {
              cur += v[i1][i2][i].first;
              break;
            }
            if (1 + i == v[i1][i2].size()) {
              res = false;
            }
          }
          for (int i = 0; i < v[i2][i3].size(); ++i) {
            if (v[i2][i3][i].second != 1 && v[i2][i3][i].second != i1 &&
                v[i2][i3][i].second != i2 && v[i2][i3][i].second != i3) {
              cur += v[i2][i3][i].first;
              break;
            }
            if (1 + i == v[i2][i3].size()) {
              res = false;
            }
          }
          for (int i = 0; i < v[i3][1].size(); ++i) {
            if (v[i3][1][i].second != 1 && v[i3][1][i].second != i1 &&
                v[i3][1][i].second != i2 && v[i3][1][i].second != i3) {
              cur += v[i3][1][i].first;
              break;
            }
            if (1 + i == v[i3][1].size()) {
              res = false;
            }
          }
          if (res) ans = min(ans, cur);
        }
      }
    }
    cout << ans;
    return 0;
  }
  if (k == 10) {
    int ans = INF;
    int cur = 0;
    for (int i1 = 1; i1 <= n; ++i1) {
      for (int i2 = 1; i2 <= n; ++i2) {
        for (int i3 = 1; i3 <= n; ++i3) {
          for (int i4 = 1; i4 <= n; ++i4) {
            cur = 0;
            bool res = true;
            if (v[1][i1].empty()) {
              res = false;
            }
            if (v[i1][i2].empty()) {
              res = false;
            }
            if (v[i2][i3].empty()) {
              res = false;
            }
            if (v[i3][i4].empty()) {
              res = false;
            }
            if (v[i4][1].empty()) {
              res = false;
            }
            for (int i = 0; i < v[1][i1].size(); ++i) {
              if (v[1][i1][i].second != 1 && v[1][i1][i].second != i1 &&
                  v[1][i1][i].second != i2 && v[1][i1][i].second != i3 &&
                  v[1][i1][i].second != i4) {
                cur += v[1][i1][i].first;
                break;
              }
              if (1 + i == v[1][i1].size()) {
                res = false;
              }
            }
            for (int i = 0; i < v[i1][i2].size(); ++i) {
              if (v[i1][i2][i].second != 1 && v[i1][i2][i].second != i1 &&
                  v[i1][i2][i].second != i2 && v[i1][i2][i].second != i3 &&
                  v[i1][i2][i].second != i4) {
                cur += v[i1][i2][i].first;
                break;
              }
              if (1 + i == v[i1][i2].size()) {
                res = false;
              }
            }
            for (int i = 0; i < v[i2][i3].size(); ++i) {
              if (v[i2][i3][i].second != 1 && v[i2][i3][i].second != i1 &&
                  v[i2][i3][i].second != i2 && v[i2][i3][i].second != i3 &&
                  v[i2][i3][i].second != i4) {
                cur += v[i2][i3][i].first;
                break;
              }
              if (1 + i == v[i2][i3].size()) {
                res = false;
              }
            }
            for (int i = 0; i < v[i3][i4].size(); ++i) {
              if (v[i3][i4][i].second != 1 && v[i3][i4][i].second != i1 &&
                  v[i3][i4][i].second != i2 && v[i3][i4][i].second != i3 &&
                  v[i3][i4][i].second != i4) {
                cur += v[i3][i4][i].first;
                break;
              }
              if (1 + i == v[i3][i4].size()) {
                res = false;
              }
            }
            for (int i = 0; i < v[i4][1].size(); ++i) {
              if (v[i4][1][i].second != 1 && v[i4][1][i].second != i1 &&
                  v[i4][1][i].second != i2 && v[i4][1][i].second != i3 &&
                  v[i4][1][i].second != i4) {
                cur += v[i4][1][i].first;
                break;
              }
              if (1 + i == v[i4][1].size()) {
                res = false;
              }
            }
            if (res) ans = min(ans, cur);
          }
        }
      }
    }
    cout << ans;
    return 0;
  }
}

### Prompt

Please create a solution in CPP to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
const int size1 = 4e5;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  static int g[81][81], g1[81][81];
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cin >> g[i][j];
      g1[j][i] = g[i][j];
    }
  }
  const int c = 81;
  vector<vector<vector<pair<int, int>>>> v(c);
  for (int i = 0; i < 81; ++i) {
    v[i].resize(c);
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      for (int k = 1; k <= n; ++k) {
        if (k != i && k != j) {
          v[i][j].push_back({g[i][k] + g[k][j], k});
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      sort(v[i][j].begin(), v[i][j].end());
    }
  }
  if (k == 2) {
    cout << v[1][1][0].first;
    return 0;
  }
  const int INF = 2e9;
  if (k == 4) {
    int ans = INF;
    int cur = 0;
    for (int i1 = 1; i1 <= n; ++i1) {
      cur = 0;
      bool res = true;
      if (v[1][i1].empty()) {
        res = false;
      }
      if (v[i1][1].empty()) {
        res = false;
      }
      for (int i = 0; i < v[1][i1].size(); ++i) {
        if (v[1][i1][i].second != 1 && v[1][i1][i].second != i1) {
          cur += v[1][i1][i].first;
          break;
        }
        if (1 + i == v[1][i1].size()) {
          res = false;
        }
      }
      for (int i = 0; i < v[i1][1].size(); ++i) {
        if (v[i1][1][i].second != 1 && v[i1][1][i].second != i1) {
          cur += v[i1][1][i].first;
          break;
        }
        if (1 + i == v[i1][1].size()) {
          res = false;
        }
      }
      if (res) ans = min(ans, cur);
    }
    cout << ans;
    return 0;
  }
  if (k == 6) {
    int ans = INF;
    int cur = 0;
    for (int i1 = 1; i1 <= n; ++i1) {
      for (int i2 = 1; i2 <= n; ++i2) {
        cur = 0;
        bool res = true;
        if (v[1][i1].empty()) {
          res = false;
        }
        if (v[i1][i2].empty()) {
          res = false;
        }
        if (v[i2][1].empty()) {
          res = false;
        }
        for (int i = 0; i < v[1][i1].size(); ++i) {
          if (v[1][i1][i].second != 1 && v[1][i1][i].second != i1 &&
              v[1][i1][i].second != i2) {
            cur += v[1][i1][i].first;
            break;
          }
          if (1 + i == v[1][i1].size()) {
            res = false;
          }
        }
        for (int i = 0; i < v[i1][i2].size(); ++i) {
          if (v[i1][i2][i].second != 1 && v[i1][i2][i].second != i1 &&
              v[i1][i2][i].second != i2) {
            cur += v[i1][i2][i].first;
            break;
          }
          if (1 + i == v[i1][i2].size()) {
            res = false;
          }
        }
        for (int i = 0; i < v[i2][1].size(); ++i) {
          if (v[i2][1][i].second != 1 && v[i2][1][i].second != i1 &&
              v[i2][1][i].second != i2) {
            cur += v[i2][1][i].first;
            break;
          }
          if (1 + i == v[i2][1].size()) {
            res = false;
          }
        }
        if (res) ans = min(ans, cur);
      }
    }
    cout << ans;
    return 0;
  }
  if (k == 8) {
    int ans = INF;
    int cur = 0;
    for (int i1 = 1; i1 <= n; ++i1) {
      for (int i2 = 1; i2 <= n; ++i2) {
        for (int i3 = 1; i3 <= n; ++i3) {
          cur = 0;
          bool res = true;
          if (v[1][i1].empty()) {
            res = false;
          }
          if (v[i1][i2].empty()) {
            res = false;
          }
          if (v[i2][i3].empty()) {
            res = false;
          }
          if (v[i3][1].empty()) {
            res = false;
          }
          for (int i = 0; i < v[1][i1].size(); ++i) {
            if (v[1][i1][i].second != 1 && v[1][i1][i].second != i1 &&
                v[1][i1][i].second != i2 && v[1][i1][i].second != i3) {
              cur += v[1][i1][i].first;
              break;
            }
            if (1 + i == v[1][i1].size()) {
              res = false;
            }
          }
          for (int i = 0; i < v[i1][i2].size(); ++i) {
            if (v[i1][i2][i].second != 1 && v[i1][i2][i].second != i1 &&
                v[i1][i2][i].second != i2 && v[i1][i2][i].second != i3) {
              cur += v[i1][i2][i].first;
              break;
            }
            if (1 + i == v[i1][i2].size()) {
              res = false;
            }
          }
          for (int i = 0; i < v[i2][i3].size(); ++i) {
            if (v[i2][i3][i].second != 1 && v[i2][i3][i].second != i1 &&
                v[i2][i3][i].second != i2 && v[i2][i3][i].second != i3) {
              cur += v[i2][i3][i].first;
              break;
            }
            if (1 + i == v[i2][i3].size()) {
              res = false;
            }
          }
          for (int i = 0; i < v[i3][1].size(); ++i) {
            if (v[i3][1][i].second != 1 && v[i3][1][i].second != i1 &&
                v[i3][1][i].second != i2 && v[i3][1][i].second != i3) {
              cur += v[i3][1][i].first;
              break;
            }
            if (1 + i == v[i3][1].size()) {
              res = false;
            }
          }
          if (res) ans = min(ans, cur);
        }
      }
    }
    cout << ans;
    return 0;
  }
  if (k == 10) {
    int ans = INF;
    int cur = 0;
    for (int i1 = 1; i1 <= n; ++i1) {
      for (int i2 = 1; i2 <= n; ++i2) {
        for (int i3 = 1; i3 <= n; ++i3) {
          for (int i4 = 1; i4 <= n; ++i4) {
            cur = 0;
            bool res = true;
            if (v[1][i1].empty()) {
              res = false;
            }
            if (v[i1][i2].empty()) {
              res = false;
            }
            if (v[i2][i3].empty()) {
              res = false;
            }
            if (v[i3][i4].empty()) {
              res = false;
            }
            if (v[i4][1].empty()) {
              res = false;
            }
            for (int i = 0; i < v[1][i1].size(); ++i) {
              if (v[1][i1][i].second != 1 && v[1][i1][i].second != i1 &&
                  v[1][i1][i].second != i2 && v[1][i1][i].second != i3 &&
                  v[1][i1][i].second != i4) {
                cur += v[1][i1][i].first;
                break;
              }
              if (1 + i == v[1][i1].size()) {
                res = false;
              }
            }
            for (int i = 0; i < v[i1][i2].size(); ++i) {
              if (v[i1][i2][i].second != 1 && v[i1][i2][i].second != i1 &&
                  v[i1][i2][i].second != i2 && v[i1][i2][i].second != i3 &&
                  v[i1][i2][i].second != i4) {
                cur += v[i1][i2][i].first;
                break;
              }
              if (1 + i == v[i1][i2].size()) {
                res = false;
              }
            }
            for (int i = 0; i < v[i2][i3].size(); ++i) {
              if (v[i2][i3][i].second != 1 && v[i2][i3][i].second != i1 &&
                  v[i2][i3][i].second != i2 && v[i2][i3][i].second != i3 &&
                  v[i2][i3][i].second != i4) {
                cur += v[i2][i3][i].first;
                break;
              }
              if (1 + i == v[i2][i3].size()) {
                res = false;
              }
            }
            for (int i = 0; i < v[i3][i4].size(); ++i) {
              if (v[i3][i4][i].second != 1 && v[i3][i4][i].second != i1 &&
                  v[i3][i4][i].second != i2 && v[i3][i4][i].second != i3 &&
                  v[i3][i4][i].second != i4) {
                cur += v[i3][i4][i].first;
                break;
              }
              if (1 + i == v[i3][i4].size()) {
                res = false;
              }
            }
            for (int i = 0; i < v[i4][1].size(); ++i) {
              if (v[i4][1][i].second != 1 && v[i4][1][i].second != i1 &&
                  v[i4][1][i].second != i2 && v[i4][1][i].second != i3 &&
                  v[i4][1][i].second != i4) {
                cur += v[i4][1][i].first;
                break;
              }
              if (1 + i == v[i4][1].size()) {
                res = false;
              }
            }
            if (res) ans = min(ans, cur);
          }
        }
      }
    }
    cout << ans;
    return 0;
  }
}

```