만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

강의실

면접 대비

시간 제한1초메모리 제한1024 MB

요약
직선 위에 있는 N개 강의실의 좌표와 최대 K번의 순간이동이 주어질 때, 0에서 출발해 모든 강의실을 방문하는 최소 이동 시간을 구합니다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 힙
정답자
아직 제출이 없습니다

문제

혁준이는 오늘 학교에서 NN개의 강의를 들어야 한다. 모든 강의는 xx축 위의 서로 다른 좌표에 있는 강의실에서 진행된다. ii번째 강의실은 x=Aix = A_i에 있고, 혁준이는 처음에 x=0x = 0에 있다. 혁준이가 xx축 위에서 왼쪽 또는 오른쪽으로 11만큼 이동할 때마다 11초가 걸린다. 혁준이는 초급 마법사라서 최대 KK번 순간이동을 할 수 있다. 순간이동을 하면 현재 위치에서 원하는 다른 위치로 즉시 이동하며, 이때는 시간이 걸리지 않는다. 혁준이가 x=0x = 0에서 출발하여 모든 강의실을 한 번씩 들르는 데 걸리는 최소 시간을 구하시오. 강의를 듣는 데는 시간이 걸리지 않는다.

입력

첫 번째 줄에 정수 NN, KK가 주어진다. (1≤N≤100 0001 \le N \le 100\,000; 0≤K≤N0 \le K \le N)

다음 줄에 강의실의 위치를 나타내는 서로 다른 정수 AiA_i가 공백으로 구분되어 주어진다. (1≤Ai≤1091 \le A_i \le 10^{9})

출력

혁준이가 모든 강의실을 한 번씩 들르는 데 걸리는 최소 시간을 출력한다.

예제1

  1. 예제 1

    입력
    6 3
    4 9 1 14 5 6
    
    예상 출력
    3