Description

小明的书架上放了许多书，为了使书架变得整洁，小明决定整理书架，他将 所有书按高度大小排列，这样排了之后虽然整齐了许多，但小明发现，书本的宽 度不同，导致书架看上去还是有些凌乱。小明把这个凌乱值定义为相邻两本书的 宽度差的绝对值的和。

例如有 4 本书：

1×2

5×3

2×4

3×l

那么小明将其排列整齐后的顺序是：

1×2

2×4

3×l

5x3

凌乱值就是 2+3+2=7。

于是小明决定拿掉其中的 k 本书，使凌乱值最小，你能帮他求出这个最小值 吗？已知每本书的高度都不一样。

Format

Input

第一行两个数字 n 和 k，代表书总共有 n 本，要求从中去掉 k 本。(l≤n≤ 100，1≤k<n)。下面的 n 行，每行两个数字表示一本书的高度和宽度，它们均小 于 200。

Output

一行一个整数，表示书架的最小凌乱值。

Samples

4 1
1 2
2 4
3 1
5 3

3

Limitation

30%的数据，n≤20。

100%的数据，n≤l00．k<n。