E - Exhibition Booth Arrangement Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は N 社が出展する展示会の運営を担当しています。会場には円形に配置された N 個のブースがあり、時計回りに 1 から N まで番号が付けられています。円形配置のため、ブース k とブース k+1（ 1 \leq k \leq N-1 ）が隣接しているほか、ブース N とブース 1 も隣接しています。したがって、隣接するブースのペアはちょうど N 組あります。

N 社の企業にも 1 から N まで番号が付けられており、最初、企業 i はブース i に配置されています（ 1 \leq i \leq N ）。各ブースにはちょうど 1 社が入り、各企業はちょうど 1 つのブースを使用します。

展示会では、隣接するブースのペアそれぞれについて、そこに配置された 2 社がコラボレーション企画を行います。企業 i と企業 j がコラボレーションした場合の集客効果は C_{i,j} で表されます（ C_{i,j} = C_{j,i} ）。

高橋君は、異なる 2 社の企業を選び、それぞれが現在使用しているブースを互いに交換する操作を、0 回以上 K 回以下行うことができます。各操作で選ぶ 2 社に制限はなく、ある企業が複数回の操作で選ばれることや、同じ企業のペアが複数回選ばれることも許されます。

すべての操作を終えた後の配置を考えます。操作後にブース k に配置されている企業を p_k とすると、(p_1, p_2, \ldots, p_N) は (1, 2, \ldots, N) の順列になります。このとき、隣接する N 組のブースのペアの集客効果の合計は

\sum_{k=1}^{N-1} C_{p_k, p_{k+1}} + C_{p_N, p_1}

です。操作の仕方を最適に選んだとき、この合計の最大値を求めてください。

制約

  • 3 \leq N \leq 8
  • 0 \leq K \leq \frac{N(N-1)}{2}
  • 0 \leq C_{i,j} \leq 10^6
  • C_{i,j} = C_{j,i}
  • C_{i,i} = 0
  • 入力はすべて整数

入力

N K
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
\vdots
C_{N,1} C_{N,2} \ldots C_{N,N}
  • 1 行目には、企業およびブースの数を表す整数 N と、操作の最大回数を表す整数 K が、スペース区切りで与えられる。
  • 続く N 行には、集客効果を表す N \times N の行列 C が与えられる。このうち i 行目（ 1 \leq i \leq N ）には、企業 i と各企業との集客効果 C_{i,1}, C_{i,2}, \ldots, C_{i,N} がスペース区切りで与えられる。
  • C_{i,j} = C_{j,i} および C_{i,i} = 0 が保証される。

出力

0 回以上 K 回以下の操作を行った後に達成できる、隣接するブースの全ペアの集客効果の合計の最大値を 1 行で出力せよ。

入力例 1

3 0
0 10 30
10 0 20
30 20 0

出力例 1

60

入力例 2

4 1
0 5 50 100
5 0 5 100
50 5 0 50
100 100 50 0

出力例 2

255

入力例 3

6 3
0 10 80 50 30 100
10 0 90 20 70 40
80 90 0 60 10 50
50 20 60 0 100 30
30 70 10 100 0 80
100 40 50 30 80 0

出力例 3

470

Score : 433 pts

Problem Statement

Takahashi is in charge of organizing an exhibition where N companies are exhibiting. The venue has N booths arranged in a circle, numbered 1 to N in clockwise order. Due to the circular arrangement, booth k and booth k+1 (1 \leq k \leq N-1) are adjacent, and booth N and booth 1 are also adjacent. Therefore, there are exactly N pairs of adjacent booths.

The N companies are also numbered 1 to N, and initially, company i is placed in booth i (1 \leq i \leq N). Each booth contains exactly one company, and each company uses exactly one booth.

At the exhibition, for each pair of adjacent booths, the two companies placed there will hold a collaboration event. The audience-drawing effect when company i and company j collaborate is represented by C_{i,j} (C_{i,j} = C_{j,i}).

Takahashi can perform the following operation 0 or more times, up to K times: choose two distinct companies and swap the booths they are currently using. There are no restrictions on which two companies are chosen for each operation; a company may be chosen in multiple operations, and the same pair of companies may be chosen multiple times.

Consider the arrangement after all operations are completed. Let p_k denote the company placed in booth k after the operations. Then (p_1, p_2, \ldots, p_N) is a permutation of (1, 2, \ldots, N). The total audience-drawing effect over all N pairs of adjacent booths is

$\sum_{k=1}^{N-1} C_{p_k, p_{k+1}} + C_{p_N, p_1}$

Find the maximum value of this total when the operations are chosen optimally.

Constraints

  • 3 \leq N \leq 8
  • 0 \leq K \leq \frac{N(N-1)}{2}
  • 0 \leq C_{i,j} \leq 10^6
  • C_{i,j} = C_{j,i}
  • C_{i,i} = 0
  • All inputs are integers

Input

N K
C_{1,1} C_{1,2} \ldots C_{1,N}
C_{2,1} C_{2,2} \ldots C_{2,N}
\vdots
C_{N,1} C_{N,2} \ldots C_{N,N}
  • The first line contains two space-separated integers: N, the number of companies and booths, and K, the maximum number of operations.
  • The following N lines contain the N \times N matrix C representing the audience-drawing effects. The i-th of these lines (1 \leq i \leq N) contains the space-separated values C_{i,1}, C_{i,2}, \ldots, C_{i,N}, representing the audience-drawing effects between company i and each other company.
  • It is guaranteed that C_{i,j} = C_{j,i} and C_{i,i} = 0.

Output

Print on a single line the maximum total audience-drawing effect over all pairs of adjacent booths that can be achieved after performing 0 or more and at most K operations.

Sample Input 1

3 0
0 10 30
10 0 20
30 20 0

Sample Output 1

60

Sample Input 2

4 1
0 5 50 100
5 0 5 100
50 5 0 50
100 100 50 0

Sample Output 2

255

Sample Input 3

6 3
0 10 80 50 30 100
10 0 90 20 70 40
80 90 0 60 10 50
50 20 60 0 100 30
30 70 10 100 0 80
100 40 50 30 80 0

Sample Output 3

470