시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB64454273.684%

문제

중앙대학교의 자랑스러운 청룡 푸앙이는 자신만의 별을 가지고 있다. $N$개의 정점과 $\frac{N(N-1)}{2}$개의 간선으로 이루어진 별은 무방향 완전 그래프이기 때문에 아름다운 모양을 띤다. 푸앙이는 지난번 명진이가 별의 간선을 잘라버리는 수모를 겪었기 때문에 이번에는 다른 별을 가져왔다. 이번에 가져온 별은 두 정점 $u$와 $v$를 연결하는 간선의 길이가 두 정점 번호의 곱인 $u\times v$이다.

푸앙이는 간선을 이용하여 그 간선이 잇는 두 정점을 이동할 수 있다. 푸앙이는 별 위의 $1$번 정점에서 $N$번 정점에 도착하는 여행을 떠나려고 한다. 그리고 그 사이에 $1$번 정점과 $N$번 정점이 아닌 서로 다른 $K$개의 정점을 한 번씩 방문해야 한다.

푸앙이가 별 위에서 여행할 수 있는 경로 중 이용한 간선의 길이 합이 최소가 되는 경로의 길이 합을 출력하라.

입력

첫 번째 줄에 정점의 개수 $N$과 방문해야 하는 중간 정점의 개수 $K$가 공백으로 구분되어 주어진다. $(3 \le N \le 1\,000\,000$; $0 \le K \le N-2)$

출력

첫 번째 줄에 $1$번 정점에서 시작하여 $K$개의 정점을 거쳐 $N$번 정점에 도착하는 경로 중 간선의 길이 합이 가장 작은 경로의 길이 합을 출력한다.

예제 입력 1

10 5

예제 출력 1

86

예제 입력 2

5 0

예제 출력 2

5