問題一覧 > 通常問題

No.1345 Beautiful BINGO

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 79
作問者 : maguro / テスター : KoD blackyuki PCTprobability
お気に入りにしたユーザー ProblemId : 5745 / 自分の提出
問題文最終更新日: 2021-03-24 18:53:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
灘中入試コンテストday1 (順位表) の他の問題:

Problem Statement

maguro loves puzzles. For his senior, who also loves puzzles, maguro has made a puzzle bingo.

The bingo is played on a sheet of $N \times N$ squares. Let $(i,j) \ (1 \leq i,j \leq N)$ denote the square in the $i$-th row from the top and the $j$-th column from the left.

Each square has a puzzle written on it, and to open $(i,j)$, you must solve the puzzle on that square by spending $A_{i,j}$ intellect.

Normally, completing even a single line makes a bingo, but maguro is not satisfied with an ordinary bingo. Among the $N$ columns, the $N$ rows, and the $2$ diagonals, at least $M$ of them must have all $N$ squares on them open.

Find the minimum total intellect that must be spent to satisfy this condition.

(2021/3/24) Part of the problem statement has been corrected.

Input

$N\ M$
$A_{1,1}\ A_{1,2}\ \cdots\ A_{1,N - 1}\ A_{1,N}$
$A_{2,1}\ A_{2,2}\ \cdots\ A_{2,N - 1}\ A_{2,N}$
$\vdots$
$A_{N,1}\ A_{N,2}\ \cdots\ A_{N,N - 1}\ A_{N,N}$
  • All inputs are integers.
  • $2 \leq N \leq 16$
  • $1 \leq M \leq 2N + 2$
  • $1 \leq A_{i,j} \leq 100\ (1 \leq i,j \leq N)$

Output

Output the minimum total intellect that must be spent to satisfy the condition. Print a newline at the end.

Sample

Sample 1
Input
3 2
3 1 4
1 5 9
2 6 5
Output
11

It is optimal to open $(1,1),(1,2),(1,3),(2,1),(3,1)$.

Sample 2
Input
4 3
1 9 3 2
4 1 2 5
7 2 1 6
2 9 8 1
Output
21

It is optimal to open $(1,1),(1,4),(2,1),(2,2),(2,3),(2,4),(3,2),(3,3),(4,1),(4,4)$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。