CF1310D.Tourism

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 \neq 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.

玛莎生活在一个拥有 $n$ 座城市（编号为 $1$ 到 $n$）的国家中，她住在第 $1$ 号城市。

任意两个不同城市 $i$ 和 $j$（其中 $i \neq j$）之间都存在一条直达列车线路。因此，总共有 $n(n-1)$ 条不同的线路。每条线路都有一个费用，从城市 $i$ 到城市 $j$ 的线路费用可能与从 $j$ 到 $i$ 的线路费用不同。

玛莎希望从第 $1$ 号城市出发，恰好乘坐 $k$ 条线路（每次从一座城市前往另一座城市），最终返回第 $1$ 号城市。玛莎非常节俭，因此她希望整个旅程的总费用尽可能低。为此，她不介意多次访问同一座城市，甚至不介意重复使用同一条线路。

玛莎不希望她的旅程中包含奇圈（odd cycle）。形式化地说：若存在某座被玛莎访问过的城市 $v$，使得玛莎在旅程中恰好使用了奇数条线路并最终回到城市 $v$，则该旅程被视为失败。

请帮助玛莎找出总费用最小（即所有所选线路费用之和最小）的成功旅程。

First line of input had two integer numbers $n,k$ ($2 \leq n \leq 80; 2 \leq k \leq 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 \neq j$, and is 0 otherwise (there are no routes $i \to i$). All route costs are integers from $0$ to $10^8$.

输入的第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 80$；$2 \leq k \leq 10$）：分别表示该国的城市数量以及玛莎旅行中的路线数量。保证 $k$ 为偶数。

接下来的 $n$ 行描述了各条路线：第 $i$ 行中的第 $j$ 个数字表示从城市 $i$ 到城市 $j$ 的路线费用（当 $i \neq j$ 时），否则为 $0$（即不存在从城市 $i$ 到其自身的路线）。所有路线费用均为 $0$ 到 $10^8$ 之间的整数。

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

输出一个整数——玛莎成功旅程的最低总花费。