게임을 클리어하자

산지니는 게임 '엘든 링'을 즐겨 한다. 이 게임은 즐길 거리가 많아서 처음부터 다시 시작하는 회차 플레이가 유행이다. 한 번 클리어하면 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$)

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

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