/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は、横一列に並んだ N 枚の板からなるフェンスをペンキで塗ることにしました。
板には左から順に 1 から N までの番号が付けられています。
使用できるペンキの色は 1 から K までの K 種類あります。
高橋君は、それぞれの板をちょうど 1 つの色で塗ります。
板 i を色 j で塗るには、コストが C_{i, j} かかります。
また、見栄えを良くするため、隣り合う板を同じ色で塗ることはできません。すなわち、すべての 1 \leq i \leq N - 1 について、板 i と板 i + 1 は異なる色で塗る必要があります。
すべての板を条件を満たすように塗るとき、かかるコストの総和の最小値を求めてください。
制約
- 1 \leq N \leq 10^5
- 2 \leq K \leq 10^6
- N \times K \leq 10^6
- 1 \leq C_{i, j} \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K
C_{1, 1} C_{1, 2} \dots C_{1, K}
C_{2, 1} C_{2, 2} \dots C_{2, K}
\vdots
C_{N, 1} C_{N, 2} \dots C_{N, K}
出力
すべての板を条件を満たすように塗る際にかかるコストの総和の最小値を 1 行で出力してください。
入力例 1
3 3 2 5 5 1 100 100 100 1 100
出力例 1
7
入力例 2
4 2 3 5 2 8 9 4 1 7
出力例 2
12
入力例 3
8 4 12 45 67 23 89 34 11 56 78 90 21 43 15 63 82 99 44 12 77 35 68 29 51 14 93 84 37 62 19 73 48 85
出力例 3
163
入力例 4
12 4 837204918 294817263 948172635 182736452 718293041 492018273 618294031 384729102 529103847 819203948 203948172 638291047 192837465 748392018 382910475 920184736 482910374 192847563 839201746 573829104 628194038 394820174 182739405 748392019 918273645 538291047 284719203 401928374 284910385 619284730 847291038 193847562 394820174 728194039 501928374 819283746 182739405 492817364 738291048 394820175 618294037 839201745 294810385 501928374 748392018 193847562 482910375 628194039
出力例 4
3307291815
入力例 5
1 2 100 42
出力例 5
42
Score : 400 pts
Problem Statement
Takahashi has decided to paint a fence consisting of N boards arranged in a row from left to right.
The boards are numbered 1 through N from left to right.
There are K available colors of paint, numbered 1 through K.
Takahashi will paint each board with exactly one color.
Painting board i with color j costs C_{i, j}.
Furthermore, to make the fence look nice, no two adjacent boards can be painted with the same color. That is, for all 1 \leq i \leq N - 1, board i and board i + 1 must be painted with different colors.
Find the minimum total cost to paint all the boards such that the condition is satisfied.
Constraints
- 1 \leq N \leq 10^5
- 2 \leq K \leq 10^6
- N \times K \leq 10^6
- 1 \leq C_{i, j} \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
C_{1, 1} C_{1, 2} \dots C_{1, K}
C_{2, 1} C_{2, 2} \dots C_{2, K}
\vdots
C_{N, 1} C_{N, 2} \dots C_{N, K}
Output
Print the minimum total cost to paint all the boards satisfying the condition in a single line.
Sample Input 1
3 3 2 5 5 1 100 100 100 1 100
Sample Output 1
7
Sample Input 2
4 2 3 5 2 8 9 4 1 7
Sample Output 2
12
Sample Input 3
8 4 12 45 67 23 89 34 11 56 78 90 21 43 15 63 82 99 44 12 77 35 68 29 51 14 93 84 37 62 19 73 48 85
Sample Output 3
163
Sample Input 4
12 4 837204918 294817263 948172635 182736452 718293041 492018273 618294031 384729102 529103847 819203948 203948172 638291047 192837465 748392018 382910475 920184736 482910374 192847563 839201746 573829104 628194038 394820174 182739405 748392019 918273645 538291047 284719203 401928374 284910385 619284730 847291038 193847562 394820174 728194039 501928374 819283746 182739405 492817364 738291048 394820175 618294037 839201745 294810385 501928374 748392018 193847562 482910375 628194039
Sample Output 4
3307291815
Sample Input 5
1 2 100 42
Sample Output 5
42