#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using pii = std::pair<int, int>;
template <typename T>
static inline T gcd(T a, T b) {
  a = std::abs(a);
  b = std::abs(b);
  while (b > 0) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
template <typename T>
static inline T sqr(T a) {
  return a * a;
}
template <typename T>
static inline bool remin(T &a, const T &val) {
  if (a > val) {
    a = val;
    return true;
  }
  return false;
}
template <typename T>
static inline bool remax(T &a, const T &val) {
  if (a < val) {
    a = val;
    return true;
  }
  return false;
}
static inline ll nxt() {
  int64_t first;
  scanf("%" PRId64, &first);
  return first;
}
static inline void skipEndLine() {
  char c = getchar();
  while (c != '\n') {
    c = getchar();
  }
}
static inline std::string nxtLine() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (c == '\n' || c == '\r' || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static inline std::string nxtString() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (!isspace(c)) {
      break;
    }
  }
  if (c == -1) {
    return ret;
  }
  ret.push_back(c);
  while (true) {
    c = getchar();
    if (isspace(c) || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static std::chrono::system_clock::time_point clock_t0;
static inline void init_time() { clock_t0 = std::chrono::system_clock::now(); }
static inline double get_time() {
  auto t = std::chrono::system_clock::now();
  return std::chrono::duration<double>((t - clock_t0)).count();
}
static inline void print_time(const std::string &name) {
  std::cerr << name << " " << get_time() << "s." << std::endl;
}
template <class T>
static inline T pw(T a, ll n) {
  T ret = T(1);
  while (n > 0) {
    if (n & 1) ret = ret * a;
    a = a * a;
    n >>= 1;
  }
  return ret;
}
static inline ll pw(ll a, ll n, ll m) {
  a %= m;
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret = ret * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return ret;
}
class ThreadPool {
 public:
  ThreadPool(size_t);
  template <class F, class... Args>
  auto enqueue(F &&f, Args &&...args)
      -> std::future<typename std::result_of<F(Args...)>::type>;
  ~ThreadPool();

 private:
  std::vector<std::thread> workers;
  std::queue<std::function<void()>> tasks;
  std::mutex queue_mutex;
  std::condition_variable condition;
  bool stop;
};
inline ThreadPool::ThreadPool(size_t threads) : stop(false) {
  for (size_t i = 0; i < threads; ++i) {
    auto f = [this] {
      for (;;) {
        std::function<void()> task;
        {
          std::unique_lock<std::mutex> lock(this->queue_mutex);
          this->condition.wait(
              lock, [this] { return this->stop || !this->tasks.empty(); });
          if (this->stop && this->tasks.empty()) return;
          task = std::move(this->tasks.front());
          this->tasks.pop();
        }
        task();
      }
    };
    workers.emplace_back(f);
  }
}
template <class F, class... Args>
auto ThreadPool::enqueue(F &&f, Args &&...args)
    -> std::future<typename std::result_of<F(Args...)>::type> {
  using return_type = typename std::result_of<F(Args...)>::type;
  auto task = std::make_shared<std::packaged_task<return_type()>>(
      std::bind(std::forward<F>(f), std::forward<Args>(args)...));
  std::future<return_type> res = task->get_future();
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    if (stop) {
      throw std::runtime_error("enqueue on stopped ThreadPool");
    }
    tasks.emplace([task]() { (*task)(); });
  }
  condition.notify_one();
  return res;
}
inline ThreadPool::~ThreadPool() {
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    stop = true;
  }
  condition.notify_all();
  for (std::thread &worker : workers) {
    worker.join();
  }
}
static const ll ten9 = 1000 * 1000 * 1000;
template <class T>
struct Point2d {
  T first{0}, second{0};
  Point2d() = default;
  Point2d(T first, T second) : first(first), second(second) {}
  Point2d operator-(const Point2d &r) const {
    return Point2d(first - r.first, second - r.second);
  }
  Point2d operator+(const Point2d &r) const {
    return Point2d(first + r.first, second + r.second);
  }
  Point2d operator*(const T &r) const { return Point2d(first * r, second * r); }
  bool operator<(const Point2d &p) const {
    if (first != p.first) return first < p.first;
    return second < p.second;
  }
  bool operator<=(const Point2d &p) const {
    if (first != p.first) return first <= p.first;
    return second <= p.second;
  }
  bool operator==(const Point2d &p) const {
    return first == p.first && second == p.second;
  }
  bool operator!=(const Point2d &p) const {
    return first != p.first || second != p.second;
  }
  bool operator>(const Point2d &p) const {
    if (first != p.first) return first > p.first;
    return second > p.second;
  }
  bool operator>=(const Point2d &p) const {
    if (first != p.first) return first >= p.first;
    return second >= p.second;
  }
  T sqlen() const { return first * first + second * second; }
  ld len() const { return sqrtl(sqlen()); }
};
template <class T>
static inline T dot(const Point2d<T> &l, const Point2d<T> &r) {
  return l.first * r.first + l.second * r.second;
}
template <class T>
static inline T cross(const Point2d<T> &l, const Point2d<T> &r) {
  return l.first * r.second - l.second * r.first;
}
template <class T>
struct Fenwick {
  std::vector<T> t;
  inline void init(int n) { t.assign(n, T(0)); }
  inline void inc(int p, T val) {
    for (; p < t.size(); p |= (p + 1)) {
      t[p] += val;
    }
  }
  inline T sum(int r) {
    T result = 0;
    for (; r >= 0; r &= (r + 1), --r) {
      result += t[r];
    }
    return result;
  }
  inline T sum(int l, int r) { return sum(r) - sum(l - 1); }
  inline void clear() {
    for (int &v : t) {
      v = T(0);
    }
  }
};
static const ld PI = acosl(-1.0);
static const ll mod = ten9 + 7;
using pt = Point2d<ll>;
using ptd = Point2d<ld>;
static std::mt19937_64 generator{123123};
using namespace std;
void prepare() {}
pair<vector<int>, vector<int>> make_matches(const vector<int> &a,
                                            const vector<char> &used,
                                            int &ans) {
  vector<int> winners;
  winners.reserve(a.size() / 2);
  vector<int> loosers;
  loosers.reserve(a.size() / 2);
  for (int i = 0; i < a.size(); i += 2) {
    if (used[a[i]] || used[a[i + 1]]) {
      ans++;
    }
    if (used[a[i]]) {
      winners.push_back(a[i]);
      loosers.push_back(a[i + 1]);
    } else {
      winners.push_back(a[i + 1]);
      loosers.push_back(a[i]);
    }
  }
  return make_pair(winners, loosers);
}
void solve() {
  int n = nxt();
  int k = nxt();
  ll inf = LLONG_MAX / 2;
  ll ans = inf;
  vector<vector<ll>> a(n, vector<ll>(n));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      a[i][j] = nxt();
    }
    a[i][i] = inf;
  }
  int it = 10000;
  vector<int> p(n);
  for (int i = 0; i < n; ++i) {
    p[i] = i;
  }
  while (it--) {
    shuffle(p.begin(), p.end(), generator);
    vector<int> l(p.begin(), p.begin() + n / 2);
    vector<int> r(p.begin() + n / 2, p.end());
    bool is_one = false;
    for (int v : l) {
      if (v == 0) {
        is_one = true;
      }
    }
    if (!is_one) {
      swap(l, r);
    }
    vector<ll> LD(l.size(), inf);
    vector<ll> RD(r.size(), inf);
    int id_one = -1;
    for (int i = 0; i < l.size(); ++i) {
      if (l[i] == 0) {
        id_one = i;
        LD[i] = 0;
      }
    }
    for (int t = 0; t < k; ++t) {
      for (int i = 0; i < l.size(); ++i) {
        for (int j = 0; j < r.size(); ++j) {
          RD[j] = min(RD[j], LD[i] + a[l[i]][r[j]]);
        }
      }
      LD.swap(RD);
      l.swap(r);
      for (int j = 0; j < r.size(); ++j) {
        RD[j] = inf;
      }
    }
    ans = min(ans, LD[id_one]);
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  init_time();
  prepare();
  int t = 1;
  for (int i = 0; i < t; ++i) {
    solve();
  }
  print_time("Time:");
  return 0;
}

### Prompt

Your task is to create a cpp solution 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 ll = long long;
using ld = long double;
using pii = std::pair<int, int>;
template <typename T>
static inline T gcd(T a, T b) {
  a = std::abs(a);
  b = std::abs(b);
  while (b > 0) {
    a %= b;
    std::swap(a, b);
  }
  return a;
}
template <typename T>
static inline T sqr(T a) {
  return a * a;
}
template <typename T>
static inline bool remin(T &a, const T &val) {
  if (a > val) {
    a = val;
    return true;
  }
  return false;
}
template <typename T>
static inline bool remax(T &a, const T &val) {
  if (a < val) {
    a = val;
    return true;
  }
  return false;
}
static inline ll nxt() {
  int64_t first;
  scanf("%" PRId64, &first);
  return first;
}
static inline void skipEndLine() {
  char c = getchar();
  while (c != '\n') {
    c = getchar();
  }
}
static inline std::string nxtLine() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (c == '\n' || c == '\r' || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static inline std::string nxtString() {
  std::string ret;
  char c = '\n';
  while (true) {
    c = getchar();
    if (!isspace(c)) {
      break;
    }
  }
  if (c == -1) {
    return ret;
  }
  ret.push_back(c);
  while (true) {
    c = getchar();
    if (isspace(c) || c == -1) {
      break;
    }
    ret.push_back(c);
  }
  return ret;
}
static std::chrono::system_clock::time_point clock_t0;
static inline void init_time() { clock_t0 = std::chrono::system_clock::now(); }
static inline double get_time() {
  auto t = std::chrono::system_clock::now();
  return std::chrono::duration<double>((t - clock_t0)).count();
}
static inline void print_time(const std::string &name) {
  std::cerr << name << " " << get_time() << "s." << std::endl;
}
template <class T>
static inline T pw(T a, ll n) {
  T ret = T(1);
  while (n > 0) {
    if (n & 1) ret = ret * a;
    a = a * a;
    n >>= 1;
  }
  return ret;
}
static inline ll pw(ll a, ll n, ll m) {
  a %= m;
  ll ret = 1;
  while (n > 0) {
    if (n & 1) ret = ret * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return ret;
}
class ThreadPool {
 public:
  ThreadPool(size_t);
  template <class F, class... Args>
  auto enqueue(F &&f, Args &&...args)
      -> std::future<typename std::result_of<F(Args...)>::type>;
  ~ThreadPool();

 private:
  std::vector<std::thread> workers;
  std::queue<std::function<void()>> tasks;
  std::mutex queue_mutex;
  std::condition_variable condition;
  bool stop;
};
inline ThreadPool::ThreadPool(size_t threads) : stop(false) {
  for (size_t i = 0; i < threads; ++i) {
    auto f = [this] {
      for (;;) {
        std::function<void()> task;
        {
          std::unique_lock<std::mutex> lock(this->queue_mutex);
          this->condition.wait(
              lock, [this] { return this->stop || !this->tasks.empty(); });
          if (this->stop && this->tasks.empty()) return;
          task = std::move(this->tasks.front());
          this->tasks.pop();
        }
        task();
      }
    };
    workers.emplace_back(f);
  }
}
template <class F, class... Args>
auto ThreadPool::enqueue(F &&f, Args &&...args)
    -> std::future<typename std::result_of<F(Args...)>::type> {
  using return_type = typename std::result_of<F(Args...)>::type;
  auto task = std::make_shared<std::packaged_task<return_type()>>(
      std::bind(std::forward<F>(f), std::forward<Args>(args)...));
  std::future<return_type> res = task->get_future();
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    if (stop) {
      throw std::runtime_error("enqueue on stopped ThreadPool");
    }
    tasks.emplace([task]() { (*task)(); });
  }
  condition.notify_one();
  return res;
}
inline ThreadPool::~ThreadPool() {
  {
    std::unique_lock<std::mutex> lock(queue_mutex);
    stop = true;
  }
  condition.notify_all();
  for (std::thread &worker : workers) {
    worker.join();
  }
}
static const ll ten9 = 1000 * 1000 * 1000;
template <class T>
struct Point2d {
  T first{0}, second{0};
  Point2d() = default;
  Point2d(T first, T second) : first(first), second(second) {}
  Point2d operator-(const Point2d &r) const {
    return Point2d(first - r.first, second - r.second);
  }
  Point2d operator+(const Point2d &r) const {
    return Point2d(first + r.first, second + r.second);
  }
  Point2d operator*(const T &r) const { return Point2d(first * r, second * r); }
  bool operator<(const Point2d &p) const {
    if (first != p.first) return first < p.first;
    return second < p.second;
  }
  bool operator<=(const Point2d &p) const {
    if (first != p.first) return first <= p.first;
    return second <= p.second;
  }
  bool operator==(const Point2d &p) const {
    return first == p.first && second == p.second;
  }
  bool operator!=(const Point2d &p) const {
    return first != p.first || second != p.second;
  }
  bool operator>(const Point2d &p) const {
    if (first != p.first) return first > p.first;
    return second > p.second;
  }
  bool operator>=(const Point2d &p) const {
    if (first != p.first) return first >= p.first;
    return second >= p.second;
  }
  T sqlen() const { return first * first + second * second; }
  ld len() const { return sqrtl(sqlen()); }
};
template <class T>
static inline T dot(const Point2d<T> &l, const Point2d<T> &r) {
  return l.first * r.first + l.second * r.second;
}
template <class T>
static inline T cross(const Point2d<T> &l, const Point2d<T> &r) {
  return l.first * r.second - l.second * r.first;
}
template <class T>
struct Fenwick {
  std::vector<T> t;
  inline void init(int n) { t.assign(n, T(0)); }
  inline void inc(int p, T val) {
    for (; p < t.size(); p |= (p + 1)) {
      t[p] += val;
    }
  }
  inline T sum(int r) {
    T result = 0;
    for (; r >= 0; r &= (r + 1), --r) {
      result += t[r];
    }
    return result;
  }
  inline T sum(int l, int r) { return sum(r) - sum(l - 1); }
  inline void clear() {
    for (int &v : t) {
      v = T(0);
    }
  }
};
static const ld PI = acosl(-1.0);
static const ll mod = ten9 + 7;
using pt = Point2d<ll>;
using ptd = Point2d<ld>;
static std::mt19937_64 generator{123123};
using namespace std;
void prepare() {}
pair<vector<int>, vector<int>> make_matches(const vector<int> &a,
                                            const vector<char> &used,
                                            int &ans) {
  vector<int> winners;
  winners.reserve(a.size() / 2);
  vector<int> loosers;
  loosers.reserve(a.size() / 2);
  for (int i = 0; i < a.size(); i += 2) {
    if (used[a[i]] || used[a[i + 1]]) {
      ans++;
    }
    if (used[a[i]]) {
      winners.push_back(a[i]);
      loosers.push_back(a[i + 1]);
    } else {
      winners.push_back(a[i + 1]);
      loosers.push_back(a[i]);
    }
  }
  return make_pair(winners, loosers);
}
void solve() {
  int n = nxt();
  int k = nxt();
  ll inf = LLONG_MAX / 2;
  ll ans = inf;
  vector<vector<ll>> a(n, vector<ll>(n));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      a[i][j] = nxt();
    }
    a[i][i] = inf;
  }
  int it = 10000;
  vector<int> p(n);
  for (int i = 0; i < n; ++i) {
    p[i] = i;
  }
  while (it--) {
    shuffle(p.begin(), p.end(), generator);
    vector<int> l(p.begin(), p.begin() + n / 2);
    vector<int> r(p.begin() + n / 2, p.end());
    bool is_one = false;
    for (int v : l) {
      if (v == 0) {
        is_one = true;
      }
    }
    if (!is_one) {
      swap(l, r);
    }
    vector<ll> LD(l.size(), inf);
    vector<ll> RD(r.size(), inf);
    int id_one = -1;
    for (int i = 0; i < l.size(); ++i) {
      if (l[i] == 0) {
        id_one = i;
        LD[i] = 0;
      }
    }
    for (int t = 0; t < k; ++t) {
      for (int i = 0; i < l.size(); ++i) {
        for (int j = 0; j < r.size(); ++j) {
          RD[j] = min(RD[j], LD[i] + a[l[i]][r[j]]);
        }
      }
      LD.swap(RD);
      l.swap(r);
      for (int j = 0; j < r.size(); ++j) {
        RD[j] = inf;
      }
    }
    ans = min(ans, LD[id_one]);
  }
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  init_time();
  prepare();
  int t = 1;
  for (int i = 0; i < t; ++i) {
    solve();
  }
  print_time("Time:");
  return 0;
}

```