玛莎生活在一个拥有 $$$n$$$ 城市的国家,城市编号从 $$$1$$$ 到 $$$n$$$。她住在城市号$$$1$$$。
每对不同城市 $$$i$$$ 和 $$$j$$$ 之间都有直达火车路线,其中 $$$i \neq j$$$。总共有 $$$n(n-1)$$$ 条不同的路线。每条路线都有一个成本,从 $$$i$$$ 到 $$$j$$$ 的路线成本可能与从 $$$j$$$ 到 $$$i$$$ 的路线成本不同。
玛莎想要在 $$$1$$$ 城市开始她的旅程,从一个城市到另一个城市正好采取 $$$k$$$ 路线,然后返回 $$$1$$$ 城市。玛莎在花钱方面非常谨慎,所以她希望旅程尽可能便宜。为此,玛莎不介意多次访问一座城市,甚至多次走同一条路线。
玛莎不希望她的旅程有奇怪的循环。正式来说,如果您可以选择访问玛莎城市$$$v$$$,并选择玛莎旅途中使用的奇数条路线并返回城市$$$v$$$,则该旅程被视为不成功。
帮助玛莎找到最便宜(所有路线总成本最小)的成功旅程。
输入
输入的第一行有两个整数 $$$n,k$$$ ($$$2 \leq n \leq 80; 2 \leq k \leq 10$$$):该国的城市数量和玛莎旅程中的路线数量。保证 $$$k$$$ 是偶数。
接下来的 $$$n$$$ 行保存路线描述:$$$i$$$ 行中的第 $$$j$$$ 数字表示如果 $$$i \neq j$$$ 则从 $$$i$$$ 到 $$$j$$$ 的路线成本,否则为 0(没有路线 $$$i \to i$$$)。所有路线成本均为从 $$$0$$$ 到 $$$10^8$$$ 的整数。
输出
输出一个整数——最便宜的玛莎成功旅程的总成本。
示例
输入 #1
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
输出 #1
2
输入 #2
3 2 0 1 1 2 0 1 2 2 0
输出 #2
3