This page is still under construction.

Parts of this page are still being built. What you see may change.

Grazing on the Run

Time limit1sMemory limit128 MB

Summary
Bessie starts at position L and walks a line to eat N grass clumps; minimize the sum of times at which each clump is eaten.
Level

Medium6 of 10

Topics
Dynamic programming, Intervals, Greedy
Solved
No attempts yet

Problem

Picture a long, straight pasture as a number line. On this line there are NN clumps of grass (1≤N≤10001 \le N \le 1000) at distinct integer positions; treat each clump as a single point on the line.

Bessie the cow starts at an integer position LL (1≤L≤1,000,0001 \le L \le 1{,}000{,}000) and travels along the line, moving freely in either direction (reversing whenever she likes) until she has eaten every clump. She moves at a constant speed of one unit of distance per unit of time, and she eats a clump the instant she reaches its position.

A clump that goes uneaten for a while grows stale. The staleness of a clump is the amount of time that passes from the moment Bessie starts moving until she eats that clump. Bessie wants to minimize the total staleness of all the clumps.

Find the minimum possible total staleness once every clump has been eaten.

Input

The first line contains two space-separated integers NN and LL.

Each of the next NN lines contains one integer PP (1≤P≤1,000,0001 \le P \le 1{,}000{,}000), the position of a clump. All positions are distinct.

Output

Print, on a single line, the minimum total staleness Bessie can achieve after eating all of the clumps.

Examples1

  1. Example 1

    Input
    4 10
    1
    9
    11
    19
    
    Expected output
    44