Cucumberman planted N cucumbers along a straight road. Cucumbers are numbered 0 through N-1, and the position of the i-th cucumber is x[i]. The cucumbers are at pairwise distinct coordinates, but their coordinates are not necessarily in sorted order. He waters all cucumbers every day. He can't change the order of watering cucumbers, so he must water cucumber 0 first, water cucumber 1 next, and so on. (Note that this means he may be going back and forth along the road.)
Watering a cucumber takes zero time. When walking, Cucumberman needs one unit of time to travel one unit of distance. Additionally, he can build at most K teleports at any positions (including non-integer ones). If there are teleports at both P and Q, he can move from P to Q instantly using teleports.
He wants to minimize the duration between watering cucumber 0 and watering cucumber N-1. Find this minimum time, assuming that he builds and uses the K teleports optimally.
There are at most 99 test cases, terminated with EOF.
Each test case contains two lines. First line contains two numbers N,K. Second line contains n numbers,and the i-th number is x[i].
Constraints
- x will contain between 2 and 50 elements, inclusive.
- Each element of x will be between -109 and 109, inclusive.
- Elements of x will be pairwise distinct.
- K will be between 1 and 50, inclusive.
For each test case, output a number indicating the minimum time Cucumberman need.
4 2 0 6 8 2 3 1 -1000000000 1000000000 0 2 50 58 2012 12 3 9 -3 14 6 5 -9 32 7 -5 26 2 11
6 3000000000 0 58
Migrated from old NTUJ.
TCO 2012 Round 2A,450
| No. | Testdata Range | Score |
|---|