{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eMasha lives in a country with $$$n$$$ cities numbered from $$$1$$$ to $$$n$$$. She lives in the city number $$$1$$$. \u003c/p\u003e\u003cp\u003eThere is a direct train \u003cspan class\u003d\"tex-font-style-it\"\u003eroute\u003c/span\u003e 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$$$.\u003c/p\u003e\u003cp\u003eMasha wants to start her journey in city $$$1$$$, take \u003cspan class\u003d\"tex-font-style-bf\"\u003eexactly\u003c/span\u003e $$$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\u0027t mind visiting a city multiple times or even taking the same route multiple times.\u003c/p\u003e\u003cp\u003eMasha doesn\u0027t want her journey to have odd cycles. Formally, if you can select visited by Masha city $$$v$$$, take \u003cspan class\u003d\"tex-font-style-bf\"\u003eodd\u003c/span\u003e number of routes used by Masha in her journey and return to the city $$$v$$$, such journey is considered unsuccessful.\u003c/p\u003e\u003cp\u003eHelp Masha to find the cheapest (with minimal total cost of all taken routes) successful journey.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eFirst 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\u0027s journey. It is guaranteed that $$$k$$$ is even.\u003c/p\u003e\u003cp\u003eNext $$$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$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput a single integer\u0026nbsp;— total cost of the cheapest Masha\u0027s successful journey.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 8\n0 1 2 2 0\n0 0 1 1 2\n0 1 0 0 0\n2 1 1 0 0\n2 0 1 2 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2\n0 1 1\n2 0 1\n2 2 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}