나일닷컴 (Nile.Com)

배우자는 $D$일 동안 매일 인터넷에서 한 종류의 상품을 구매한다. 그가 이용하는 나일닷컴 마켓플레이스에는 $N$개의 점포가 입점해 있고, 그는 매일 그중 한 점포를 골라 쇼핑한다. 점포별 가격은 매일 바뀌므로 예정 가격이 제시되어 있다.

이 마켓플레이스에서는 같은 점포에서 2일 연속 구매하면 1할 할인을 받고, 3일 연속 구매하면 3할 할인을 받는다. 3일 이후에는 몇 일을 연속으로 구매하더라도 3할 할인이 유지된다.

절약가인 배우자를 위해 예정 가격을 바탕으로 쇼핑 계획을 세우려 한다. $D$일 동안 지불하는 총 금액이 최소가 되도록 쇼핑했을 때의 총 금액을 구하라.

입력은 $D+1$줄이다. 첫 줄에는 점포 수 $N$과 쇼핑하는 날짜 수 $D$가 공백으로 구분되어 주어진다. 단, $2 \le N \le 3000$, $2 \le D \le 365$이다.

이어지는 $D$줄에는 각각 $N$개의 10 이상 100000 이하이며 10의 배수인 수가 주어진다. 이 수들은 할인 전의 예정 가격이다. 각 줄에는 하루씩 날짜 순서대로, 한 줄 안에서는 점포 번호 순서대로 적혀 있다. 즉, $1 \le d \le D$, $1 \le n \le N$일 때, $(d+1)$번째 줄의 $n$번째 수는 $d$일에 $n$번 점포의 예정 가격이다.

표준 출력에 한 줄로 최소 합계 금액을 출력하라.