UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3405. [Usaco2009 Open]Grazing2 移动牛棚

统计 下载数据

Description

  约翰有N(2≤N≤1500)头奶牛,S(N≤S≤1,000,000)个一字排开的牛棚.相邻牛棚间的距离恰好为1.
奶牛们已经回棚休息,第i只奶牛现在待在牛棚Pi.如果两只奶牛离得太近,会让奶牛们变得很暴躁.所以约翰想给一些奶牛换一个棚,让她们之间的距离变得尽量大,并且尽管接近.令d=Trunc((s-1)/(n-1))
所以约翰希望最终的奶牛的状态是:两只相邻奶牛间的距离与d之差不超过1,而且让尽量多的间距等于d.因此,对于4只奶牛8个棚的情况,1,3,5,8或1,3,6,8这样的安置情况是允许的,而1,2,4,7或1,2,4,8这样的情况是不允许的.    帮助约翰移动奶牛,让所有奶牛的移动距离之和最小,同时让最终的安置情况符合约翰心意.

Input

    第1行输入N和S,接下来N行一行输入一个Pi.

Output

 
    一个整数,表示最小的移动距离和.

Sample Input

5 10
2
8
1
3
9

Sample Output

4

Hint

   最终移成135810.

Source

Silver