Library
InterviewTime limit1sMemory limit1024 MB
Given N shelf positions on a line and a carry limit K, find the minimum total distance walked from 0 to return all books.
Problem
You work at a library and want to put a number of books back on the shelves. The shelves are placed along the -axis. Each book's target shelf is given as an -coordinate between and , along with the maximum number of books you can carry at once. Find the shortest distance you must walk to return all books. The books start at position . You do not need to walk back after returning the last book.
Input
The first line contains two integers and , where is the number of books to return and is the number of books you can carry at once. Each of the next lines contains one integer, the -coordinate of the shelf where that book goes.
Output
Print one integer on a single line: the minimum distance you must walk to return all the books.
Hint
For example, you can start by carrying the books for shelves 3 and 4. Then fetch the book for shelf 1, and finally take the book for shelf -4.