강의실

면접 대비

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

요약
수직선 위 0에서 출발해 서로 다른 N개의 강의실을 최대 K번의 순간이동으로 모두 방문할 때 걸리는 최소 이동 시간을 구한다.
난이도

보통10점 중 6점

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

문제

혁준이는 오늘 학교에서 NN개의 강의를 들어야 한다. 모든 강의는 xx축 위의 서로 다른 좌표에 존재하는 강의실에서 진행된다.

ii번째 강의실은 x=A_ix = A\_i에 있고, 처음에 혁준이는 x=0x = 0에 있다. 혁준이가 xx축 위에서 왼쪽 또는 오른쪽으로 11만큼 이동할 때마다 11초의 시간이 걸린다.

혁준이는 초급 마법사라서 최대 KK번 순간이동을 할 수 있다. 순간이동을 하면 현재 위치에서 원하는 다른 위치로 즉시 이동하고, 시간은 소요되지 않는다.

혁준이가 x=0x = 0에서 출발하여 모든 강의실을 한 번씩 들르는 데 걸리는 최소 시간을 구해보자.

강의를 듣는 데 걸리는 시간은 없다.

입력

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

다음 줄에 강의실의 위치를 나타내는 서로 다른 정수 A_iA\_i가 공백을 사이에 두고 주어진다. (1≤A_i≤109)(1 \le A\_i \le {10}^{9})

출력

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

예제1

  1. 예제 1

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