新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:10000KB
問題 
沿線にいくつかの村がある道路がある。道路は数直線に例えられて、それぞれの村の位置は数直線上での座標（整数）として考えられる。同じ位置に、複数の村があることはない。２つの村の間の距離は、それぞれの座標の差の絶対値である。
今、郵便局が、それらの村のいくつかに（必ずしもすべての村ではない）建設されようとしている。村と、その村の郵便局は、同じ位置にある。
郵便局は、「村と、村に最も近い郵便局の間の距離」のすべての村に対する合計距離が最も短くなるように、建設されなければならない。
村の位置と、建設すべき郵便局の数が与えられたとき、「村と、村に最も近い郵便局の間の距離」のすべての村に対する合計距離の最小値を求めるプログラムを作成せよ。
入力
入力は、標準入力から読み込むこと。
入力の最初の行は、２つの整数V,Pを含んでいる。Vは、1<=V<=300を満たし、村の数を表す。Pは、1<=P<=30かつP<=Vを満たし、建設すべき郵便局の数を表す。
次の行には、V個の整数が昇順に含まれている。それぞれの整数は、村の位置（座標）を表す。各座標Xは、1<=X<=10000を満たす。
出力
出力の１行目に、「村と、村に最も近い郵便局の間の距離」のすべての村に対する合計距離の最小値を表す整数Sを出力せよ。
入力例
10 5 1 2 3 6 7 9 11 22 44 50
出力例
9
出典
IOI2000
