28017번 - 게임을 클리어하자

문제

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

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

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

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

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

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

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

입력

첫째 줄에 산지니가 게임을 몇 회차를 하는지 나타내는 수 $N$과 무기의 종류 $M$이 공백으로 구분되어 주어진다. $(2 \le N, M \le 500)$

둘째 줄부터 $N$개의 줄에는 각 무기마다 게임을 클리어하는데 걸리는 시간 $t_1, t_2, \cdots, t_M$이 공백으로 구분되어 주어진다. $(1 \le t_i \le 10,000円)$

입력으로 주어지는 모든 수는 정수이다.

출력

회차마다 효율적인 무기를 선택하였을 때 총 클리어 시간의 최솟값을 출력하라.

제한

힌트