AT_k4pc_b コミュニケーション能力(Communication Ability)

[problemUrl]: https://atcoder.jp/contests/k4pc/tasks/k4pc_b かがみずくんはかつてめちゃくちゃコミュニケーション能力が低かったため，みんなと友達になるために必要な交友関係を壊してしまいました． それからというもの，かがみずくんはその辛い経験を活かし，コミュニケーション能力を鍛え，みんなと友達になろうとしています． かがみず君も含め，かがみずくんが友達になろうとしている人々はそれぞれ自分自身のコミュニケーション能力を把握しており，１つの整数値で表されます． コミュニケーション力が違う人間同士が友達になるのは大変であり，ある人物とある人物が友達になるとき，コミュニケーション能力の差だけ労力がかかります． かがみずくんはポジティブなので，友達はもちろんのこと，友達の友達，友達の友達の友達....と，交友関係をたどってたどり着ける人物は等しく友達だと思い込んでいます． ところで，かがみずくんには謎のこだわりがあり，この順番で友達になりたい...という考えがあります．それもちゃんと達成したいです． かがみずくんは他力本願なので，他人が都合よく友達同士になってくれて，自分も都合よく友達になったときにかかる，全関係構築の労力の差の最小値を知りたいです．

> $ N $ $ M $ $ c_1 $ $ c_2 $ : $ c_N $

労力の総和の最小値を $ 1 $ 行に出力せよ.

### 課題 状況を整理しましょう．かつて $ -∞ $ だったかがみずくんのコミュニケーション能力はいまや $ M $ です．そして， $ N $ 人の人物のコミュニケーション能力は $ c_1,\ c_2,\ ...,\ c_N $ と表されます．それぞれの人のコミュニケーション能力は整数値です. 「かがみずくんがある人物と友達である」というのは，直接の友達はもちろんのこと，友達の友達，友達の友達の友達....と，交友関係をたどってたどり着ける人物である状態のことを言います． かがみずくんは $ N $ 人と友達になりたいのですが，こだわりがあるので，必ず$ 1 $ 番目の人，$ 2 $ 番目の人，...，$ N $ 番目の人，という順番に友達になりたいです． 現在，かがみずくんやその $ N $ 人は誰とも友達関係にありません．また，コミュニケーション能力が $ x $ の人物とコミュニケーション能力 $ y $ の人物が友達になるには $ |x\ -\ y| $ の労力が必要です. この状況において，かがみずくんが全員と友達になる場合において，全体でかかる労力の総和のありうる最小値を出力しなさい． ### 制約 - $ 1\ ≦\ N\ ≦\ 10^5 $. - $ 1\ ≦\ M,\ c_i\ ≦\ 10^{13} $. ### Sample Explanation 1 制約から，かがみずくんは，$ 1 $ 番目の人物，$ 2 $ 番目の人物，$ 3 $ 番目の人物と順番に友達にならなければならないことに注意せよ． - まず，$ 1 $ 番目の人物と友達になるには労力 $ |3\ -\ 2|\ =\ 1 $ が必要である. - 次に，$ 2 $ 番目の人物と友達になるための労力は, かがみずくんが $ |3\ -\ 7|\ =\ 4 $ , 人物1 が $ |2\ -\ 7|\ =\ 5 $ である. そこで, かがみずくんが友達になることで労力 $ 4 $ で友達になれる. - 同様にして，$ 1 $ 番目の人物と$ 3 $ 番目の人物が友達になることで，かがみずくんは $ |2\ -\ 1|\ =\ 1 $の労力で$ 3 $番目の人物と友達になれる． この説明を表した図が以下のようになる． !\[\](http://k4pc.contest.atcoder.jp/img/other/k4pc/B\_sample1-2.png)