백업

여러 회사가 하나의 직선 도로 위에 서로 다른 위치에 있다. 정확히 k개의 네트워크 케이블을 사용해 서로 다른 2k개 회사를 k쌍으로 묶으려고 한다.

한 회사는 두 개 이상의 쌍에 포함될 수 없다. 한 쌍을 연결하는 데 필요한 케이블의 길이는 두 회사 사이의 거리와 같다.

k쌍의 케이블 길이 합이 최소가 되도록 회사를 골라 짝지을 때, 가능한 최소 총 길이를 구하라.

첫 번째 줄에 회사의 수 n과 제공되는 케이블 수 k가 주어진다.

• 2 <= n <= 100000
• 1 <= k <= n / 2

다음 n개의 줄에는 각 회사의 위치 s가 한 줄에 하나씩 주어진다.

• 0 <= s <= 1000000000
• 위치는 작은 값부터 큰 값 순서로 주어진다.
• 두 회사가 같은 위치에 있는 경우는 없다.

서로 다른 2k개 회사를 k쌍으로 묶을 때 필요한 케이블 길이 합의 최솟값을 하나의 정수로 출력한다.