Lecture Rooms

Interview

Time limit1sMemory limit1024 MB

Summary

Given N lecture room positions on a line and at most K teleports from x=0, find the minimum walking time to visit every room.

Level: Medium6 of 10
Topics: Greedy, Sorting, Heap
Solved: No attempts yet

Problem

Hyeokjun has to attend $N$ lectures today. Every lecture is held in a lecture room at a different coordinate on the $x$ -axis. The $i$ -th lecture room is at $x = A_i$ , and Hyeokjun starts at $x = 0$ . Each move of 1 to the left or right along the $x$ -axis takes $1$ second. Hyeokjun is a novice wizard and can teleport at most $K$ times. A teleport moves him instantly from his current position to any other position he chooses, and it takes no time. Find the minimum time for Hyeokjun to start at $x = 0$ and visit every lecture room once. Attending a lecture takes no time.

Input

The first line contains integers $N$ and $K$ . ( $1 \le N \le 100\,000$ ; $0 \le K \le N$ )

The next line contains the distinct integers $A_i$ that give the positions of the lecture rooms, separated by spaces. ( $1 \le A_i \le 10^{9}$ )

Output

Print the minimum time for Hyeokjun to visit every lecture room once.

Examples1

Example 1
Input
```
6 3
4 9 1 14 5 6
```
Expected output
```
3
```