题目描述

有一个公司，在一条街上有$\red{N}$个快餐店，公司决定修$\red{K}$个仓库以满足这些快餐店的原料需求。现在给出$\red{N}$个快餐店的横坐标（他们都在一条直线上），要求修$\red{K}$个仓库，使得所有的快餐店离其对应的仓库的距离最短。仓库是建在餐厅里的。公式如下：$\red{\displaystyle\sum_{1}^{k}|d_i-(Position~of~ depot~ serving~ restaurant~ i)|}$

输入格式

第一行两个整数，$\red{N，K}$，表示有$\red{N}$个餐厅和要修$\red{K}$个仓库。其中$\red{1≤n≤700,1≤k≤30}$。接下来的$\red{N}$行，每行一个整数，表示每个餐厅的位置。它们的值不超过$\red{100000}$。

输出格式

一个整数，表示在$\red{N}$个餐厅建$\red{K}$个仓库使得所有餐厅到离其对应的仓库距离的最小值。

样例

输入样例

6 3
5
6
12
19
20
27

输出样例

8