题目描述

魔法学院的很多学员,因为过于沉迷于魔法的研究,而常常忽略生活中的很多细节,具 体表现如不修边幅,不拘小节等等。据说魔法学院著名魔法师爱恩斯坦在成名前总是穿着 破旧的衣服,朋友劝他,他说:"反正大家不认识我。"成名后,他仍是穿着破旧的衣服,朋友 劝他,他又说:"反正大家都认识我了。"

不过张琪曼是一个非常喜爱整洁的人。她有一大堆书和一个书架，想要把书放在书架 上。书架可以放下所有的书,所以张琪曼首先将书按高度顺序排列在书架上。但是发现由 于很多书的宽度不同,所以书看起来还是非常不整齐。于是她决定从中拿掉$\red{k}$本书,使得书 架可以看起来整齐一点。

书架的不整齐度是这样定义的:每两本书宽度的差的绝对值的和。例如有$\red{4}$本书:

$\red{1\times 2}$

$\red{5\times 3}$

$\red{2\times 4}$

$\red{3\times 1}$

那么将其排列整齐后是:

$\red{1\times 2}$

$\red{2\times 4}$

$\red{3\times 1}$

$\red{5\times 3}$

不整齐度就是$\red{2+3+2=7}$

已知每本书的高度都不一样，请你求出去掉$\red{k}$本书后的最小的不整齐度。

输入格式

第一行两个数字$\red{n}$和$\red{k,}$代表书有几本,从中去掉几本。$\red{(1≤}$$\red{n≤}$$\red{100,1≤}$$\red{k<n)}$ 下面的$\red{n}$行,每行两个数字表示一本书的高度和宽度,均小于$\red{200}$。

输出格式

一行一个整数，表示书架的最小不整齐度。

样例

输入样例

4 1
1 2
2 4
3 1
5 3

输出样例

3