E - Climbing to the Observation Deck Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は山の麓から山頂の展望台を目指して登山をします。

この山には N 個のチェックポイントがあり、それぞれに 1 から N までの番号が付けられています。また、麓を地点 0、山頂の展望台を地点 N+1 と表します。

高橋君は地点 0（麓）からスタートし、N 個のチェックポイントの中からいくつかを選んで立ち寄りながら登り、最終的に地点 N+1（山頂の展望台）に到達します。高橋君は常に地点番号が増加する方向にのみ移動します（したがって、各チェックポイントには高々 1 回しか立ち寄りません）。すなわち、立ち寄るチェックポイントの番号を昇順に p_1 < p_2 < \cdots < p_s とすると、高橋君は

0 \to p_1 \to p_2 \to \cdots \to p_s \to N+1

の順に移動します。s = 0（どのチェックポイントにも立ち寄らない）の場合は、地点 0 から地点 N+1 へ直接移動します。

0 \leq a < b \leq N+1 を満たす任意の 2 地点の組 (a, b) に対して、地点 a から地点 b へ途中のチェックポイントを経由せずに直接移動するためのコスト C_{a,b} が定められています。すなわち、番号が隣接していない 2 地点間であっても直接移動することができ、そのコストが与えられます。移動経路全体の消費体力は、経路上で連続する 2 地点間のコストの総和です。具体的には、上記の経路における消費体力は

C_{0,\,p_1} + C_{p_1,\,p_2} + \cdots + C_{p_{s-1},\,p_s} + C_{p_s,\,N+1}

です（s = 0 の場合は C_{0,\,N+1}）。

立ち寄るチェックポイントの選び方には以下の 2 つのルールがあります。

  1. 最小個数の条件： 立ち寄るチェックポイントの個数 s は K 個以上でなければなりません。
  2. 地形バランスの条件： 各チェックポイントは 1 から M までの番号で表される M 種類の地形タイプのうちちょうど 1 つに分類されています。1 以上 M 以下の各整数 j について、地形タイプ j に属するチェックポイントのうち立ち寄るものの個数は偶数でなければなりません（0 も偶数とみなします）。

高橋君は、上記のルールをすべて満たすようなチェックポイントの選び方のうち、消費体力を最小化したいと考えています。

ルールを満たす選び方が存在する場合は消費体力の最小値を、存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 150
  • 1 \leq M \leq 8
  • N^3 \cdot 2^M \leq 3 \times 10^8
  • 0 \leq K \leq N
  • 1 \leq t_i \leq M（1 \leq i \leq N）
  • 1 \leq C_{a,b} \leq 10^9（0 \leq a < b \leq N+1）
  • 入力はすべて整数である。

入力

N M K
t_1 t_2 \cdots t_N
C_{0,1} C_{0,2} \cdots C_{0,N+1}
C_{1,2} C_{1,3} \cdots C_{1,N+1}
\vdots
C_{N,N+1}
  • 1 行目には、チェックポイントの数 N、地形タイプの数 M、立ち寄るチェックポイントの最小個数 K が、スペース区切りで与えられる。
  • 2 行目には、各チェックポイントの地形タイプを表す t_1, t_2, \ldots, t_N がスペース区切りで与えられる。t_i はチェックポイント i の地形タイプを表す 1 以上 M 以下の整数である。M 種類すべての地形タイプが入力に現れるとは限らない。
  • 続く N + 1 行にわたって、移動コストが与えられる。これらのうち k 行目（k = 1, 2, \ldots, N+1）には、地点 k-1 を出発地点として、地点 k, k+1, \ldots, N+1 への各移動コスト C_{k-1,\,k},\, C_{k-1,\,k+1},\, \ldots,\, C_{k-1,\,N+1} がスペース区切りで与えられる。

出力

ルールを満たす立ち寄り方が存在する場合は消費体力の最小値を、存在しない場合は -1 を 1 行で出力せよ。

入力例 1

3 2 2
1 2 1
5 8 4 20
6 3 7
4 2
9

出力例 1

17

入力例 2

1 1 1
1
3 10
4

出力例 2

-1

入力例 3

8 3 3
1 2 3 1 2 3 1 2
4 9 15 7 20 18 25 30 12
6 5 11 14 9 21 17 23
8 13 4 16 19 10 22
7 12 15 6 18 20
9 3 14 11 16
5 10 8 13
6 4 9
7 5
8

出力例 3

28

入力例 4

15 5 6
1 2 3 4 5 1 2 3 4 5 1 2 3 4 1
11 25 18 40 33 52 47 60 58 75 69 88 80 95 90 110
14 9 27 22 41 36 55 50 68 63 82 77 96 91 105
13 26 12 39 31 45 44 62 57 70 66 84 79 98
8 21 34 16 48 30 53 47 65 59 78 72 90
17 11 29 24 42 37 56 51 69 64 83 78
10 23 15 36 28 49 41 54 52 71 67
19 14 32 27 46 40 58 53 72 68
12 25 20 38 33 51 45 63 60
16 9 30 22 43 35 57 49
18 13 31 26 44 39 61
7 24 19 37 32 50
15 28 10 41 34
20 12 35 29
6 27 21
18 14
9

出力例 4

100

入力例 5

1 1 0
1
1000000000 1
999999999

出力例 5

1

Score : 433 pts

Problem Statement

Takahashi is climbing a mountain from the foot to the observatory at the summit.

There are N checkpoints on this mountain, numbered 1 to N. Additionally, the foot of the mountain is represented as point 0, and the observatory at the summit is represented as point N+1.

Takahashi starts at point 0 (the foot), visits some chosen checkpoints among the N checkpoints as he climbs, and finally reaches point N+1 (the observatory at the summit). Takahashi always moves in the direction of increasing point numbers (thus, he visits each checkpoint at most once). That is, if the indices of the visited checkpoints in ascending order are p_1 < p_2 < \cdots < p_s, Takahashi moves in the following order:

0 \to p_1 \to p_2 \to \cdots \to p_s \to N+1

If s = 0 (no checkpoints are visited), he moves directly from point 0 to point N+1.

For any pair of points (a, b) satisfying 0 \leq a < b \leq N+1, a cost C_{a,b} is defined for moving directly from point a to point b without passing through any checkpoints in between. That is, direct movement is possible even between two non-adjacent points, and its cost is given. The total stamina consumption of the entire route is the sum of the costs between consecutive points on the route. Specifically, the stamina consumption for the route above is:

C_{0,\,p_1} + C_{p_1,\,p_2} + \cdots + C_{p_{s-1},\,p_s} + C_{p_s,\,N+1}

(or C_{0,\,N+1} if s = 0).

There are two rules for choosing which checkpoints to visit:

  1. Minimum Count Condition: The number of visited checkpoints s must be at least K.
  2. Terrain Balance Condition: Each checkpoint is classified into exactly one of M terrain types, represented by integers from 1 to M. For each integer j (1 \leq j \leq M), the number of visited checkpoints belonging to terrain type j must be even (where 0 is also considered even).

Takahashi wants to find a way to choose checkpoints that satisfies all the rules above while minimizing the total stamina consumption.

If there exists a valid choice of checkpoints, output the minimum stamina consumption. If no such choice exists, output -1.

Constraints

  • 1 \leq N \leq 150
  • 1 \leq M \leq 8
  • N^3 \cdot 2^M \leq 3 \times 10^8
  • 0 \leq K \leq N
  • 1 \leq t_i \leq M (1 \leq i \leq N)
  • 1 \leq C_{a,b} \leq 10^9 (0 \leq a < b \leq N+1)
  • All input values are integers.

Input

N M K
t_1 t_2 \cdots t_N
C_{0,1} C_{0,2} \cdots C_{0,N+1}
C_{1,2} C_{1,3} \cdots C_{1,N+1}
\vdots
C_{N,N+1}
  • The first line contains the number of checkpoints N, the number of terrain types M, and the minimum number of checkpoints to visit K, separated by spaces.
  • The second line contains t_1, t_2, \ldots, t_N, separated by spaces, representing the terrain types of the checkpoints. t_i is an integer between 1 and M representing the terrain type of checkpoint i. Not all M terrain types are guaranteed to appear in the input.
  • The next N + 1 lines provide the movement costs. The k-th of these lines (k = 1, 2, \ldots, N+1) contains the movement costs from point k-1 to points k, k+1, \ldots, N+1, represented as C_{k-1,\,k},\, C_{k-1,\,k+1},\, \ldots,\, C_{k-1,\,N+1}, separated by spaces.

Output

If there exists a valid way to visit checkpoints, output the minimum stamina consumption. If no such way exists, output -1 in a single line.

Sample Input 1

3 2 2
1 2 1
5 8 4 20
6 3 7
4 2
9

Sample Output 1

17

Sample Input 2

1 1 1
1
3 10
4

Sample Output 2

-1

Sample Input 3

8 3 3
1 2 3 1 2 3 1 2
4 9 15 7 20 18 25 30 12
6 5 11 14 9 21 17 23
8 13 4 16 19 10 22
7 12 15 6 18 20
9 3 14 11 16
5 10 8 13
6 4 9
7 5
8

Sample Output 3

28

Sample Input 4

15 5 6
1 2 3 4 5 1 2 3 4 5 1 2 3 4 1
11 25 18 40 33 52 47 60 58 75 69 88 80 95 90 110
14 9 27 22 41 36 55 50 68 63 82 77 96 91 105
13 26 12 39 31 45 44 62 57 70 66 84 79 98
8 21 34 16 48 30 53 47 65 59 78 72 90
17 11 29 24 42 37 56 51 69 64 83 78
10 23 15 36 28 49 41 54 52 71 67
19 14 32 27 46 40 58 53 72 68
12 25 20 38 33 51 45 63 60
16 9 30 22 43 35 57 49
18 13 31 26 44 39 61
7 24 19 37 32 50
15 28 10 41 34
20 12 35 29
6 27 21
18 14
9

Sample Output 4

100

Sample Input 5

1 1 0
1
1000000000 1
999999999

Sample Output 5

1