Under construction

Still being built. Things may change

Library

Interview

Time limit1sMemory limit1024 MB

Summary
Given N shelf positions on a line and a carry limit K, find the minimum total distance walked from 0 to return all books.
Level

Medium4 of 10

Topics
Greedy, Sorting, Array
Solved
No attempts yet

Problem

You work at a library and want to put a number of books back on the shelves. The shelves are placed along the xx-axis. Each book's target shelf is given as an xx-coordinate between −1 000-1\,000 and 1 0001\,000, 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 00. You do not need to walk back after returning the last book.

Input

The first line contains two integers NN and KK, where 1≤N≤1001 \le N \le 100 is the number of books to return and 1≤K≤1001 \le K \le 100 is the number of books you can carry at once. Each of the next NN lines contains one integer, the xx-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.

Examples1

  1. Example 1

    Input
    4 2
    3
    1
    4
    -4
    
    Expected output
    14