34250번 - 레몬이 스니켓의 위험한 대결 서브태스크

문제

재원 도시에는 높이가 $N$인 빌딩이 하나 있다. 빌딩의 외벽에는 $K$개의 기둥이 존재하며, 각각 1,ドル 2, \dots K$번 기둥이다. 어느 날 이 빌딩에 화재가 발생했고, 이를 진압하기 위해 의용 소방대 VFD (Volunteer Fire Department)가 출동하였다.

VFD는 $K$명의 대원으로 구성되어 있으며, 각 대원은 $K$개의 기둥 중 한 기둥을 맡는다. 모든 대원은 높이 0ドル$인 맨 아래에서 시작해 기둥을 타고 올라 정확히 높이 $N$에 도달해야만 화재를 완전히 진압할 수 있다.

이때 건물을 맨몸으로 오르는 것은 위험하므로, 한 사람이 높이 1ドル$만큼 오를 때마다 나머지 $K-1$명의 현재 위치와 이 사람의 새로운 위치를 줄로 연결해 안전을 확보해야 한다.

$x$번째 기둥을 담당한 대원을 $x$번째 대원이라고 하자. $x$번째 대원이 현재 높이 $H_x$에서 $H_x + 1$로 오르려 할 때, 모든 $i \ne x$에 대해 $i$번째 대원의 현재 높이 $H_i$와 $x$번째 대원의 새로운 위치 $H_x + 1$을 줄로 연결한다. 이때 각 줄의 연결 비용은 $A_{x,H_x+1} \times A_{i,H_i}$로 계산된다. 즉, 한 번의 이동에는 총 $K-1$개의 줄이 연결되며, 해당 이동의 비용은 연결 비용의 합이다.

모든 대원이 높이 $N$에 도달할 때까지 필요한 이동 비용의 합의 최솟값을 구하여라.

입력

입력은 다음과 같은 형식으로 주어진다.

$N \ K$

$A_{1,0} \ A_{1,1} \ \cdots \ A_{1,N}$

$A_{2,0} \ A_{2,1} \ \cdots \ A_{2,N}$

$\vdots$

$A_{K,0} \ A_{K,1} \ \cdots \ A_{K,N}$

출력

첫째 줄에 모든 대원이 높이 $N$에 도달하기 위한 최소 비용을 출력한다. 답은 10ドル^{18}$ 이하임이 보장된다.

제한

• 1ドル \leq N \leq 100 \ 000$.
• 2ドル \leq K \leq 200 \ 000$.
• $N \times K \leq 200 \ 000$.
• 1ドル \le A_{i,j} \le 100\ 000$ (1ドル \le i \le K,ドル 0ドル \le j \le N$).

서브태스크

힌트