레몬이 스니켓의 위험한 대결

재원시에는 높이가 $N$인 건물이 하나 있다. 건물의 외벽에는 총 $K$개의 기둥이 설치되어 있으며, 각 기둥에는 $1, 2, \dots, K$의 번호가 붙어 있다.

어느 날 건물에 화재가 발생하였고, 이를 진압하기 위해 VFD (Volunteer Fire Department)가 출동하였다.

VFD는 총 $K$명의 대원으로 구성되어 있다. 각 대원은 높이 $0$에서 출발하여 기둥을 타고 올라간다. 화재를 완전히 진압하기 위해서는 모든 대원이 높이 $N$에 도달해야 한다. 단, 각 대원은 서로 다른 기둥을 담당하여 오르며, 한 기둥에는 정확히 한 명의 대원만 배정된다.

안전 장비 없이 건물을 오르는 것은 매우 위험하다. 따라서 어떤 대원이 높이를 $1$만큼 올릴 때마다, 그 대원의 새로운 위치와 나머지 $K-1$명의 현재 위치를 밧줄로 연결하여 안전을 확보해야 한다.

보다 정확히 말하면, $x$번 기둥을 오르는 대원을 $x$번 대원이라고 하자. 현재 $x$번 대원의 높이가 $H_x$일 때, 그가 $H_x$에서 로 올라가려 한다고 하자.

이때 모든 $i \neq x$에 대해, $i$번 대원의 현재 높이 $H_i$와 $x$번 대원의 새로운 높이 을 밧줄로 연결해야 한다.

$x$번 대원의 높이 증가 과정에서 $i$번 대원과 연결하는 밧줄의 비용은

이다.

따라서 한 번의 높이 증가에는 총 $K-1$개의 밧줄이 필요하며, 해당 높이 증가의 비용은 이들 밧줄 비용의 합으로 정의된다.

모든 대원이 높이 $N$에 도달하기 위한 최소 총비용을 구하여라.

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

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

출력으로 모든 대원이 높이 $N$에 도달하기 위한 최소 총비용을 출력하여라. 답은 $10^{18}$ 이하임이 보장된다.

• $1 \leq N \leq 100\,000$
• $2 \leq K \leq 200\,000$
• $N\times K\le$