문제

산지니는 게임 '엘던 링'을 즐겨한다.

이 게임은 즐길 거리가 많기에 처음부터 게임을 다시 시작하는 회차 플레이가 유행이다. 한 번 클리어하면 1회차, 두 번 클리어하면 2회차를 돌았다고 한다.

회차마다 단검, 직검, 자검, 곡검, 마법 등 자신이 원하는 무기를 자유롭게 선택하여 시작할 수 있다.

산지니는 자존심이 강하여 회차 도중에 무기를 바꾸지 않고 끈기 있게 끝까지 클리어한다.

여러 회차를 진행할 예정인 산지니는 게임을 더 재미있게 즐기기 위해 바로 이전 회차의 무기는 사용하지 않기로 했다.

이 게임은 특이하게도 새로 시작할 때마다 능력치가 무작위로 조정되어서 자신에게 효율적인 무기가 달라진다.

최대한 효율적으로 게임을 클리어하고 싶은 산지니를 위해 최선의 무기를 선택한다면 얼마나 빨리 게임을 끝낼 수 있을지 알려주자.

# 28017
import sys
input = lambda: sys.stdin.readline().strip()

n, m = map(int, input().split())
time = [list(map(int, input().split())) for _ in range(n)]

prefix = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        
        last_time = 10 ** 9
        for a in range(1, m+1):
            if a != j:
                last_time = min(last_time, prefix[i-1][a])
                
        prefix[i][j] = last_time + time[i-1][j-1]
        
min_time = min(prefix[n][1:])
print(min_time)

백준 28017 게임을 클리어하자