样例下载

【问题描述】

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是使用积木搭建一座大厦。

幼儿园将为每个小朋友提供 $n$ 块圆柱形积木，第 $i$ 块积木的底面积为 $s_i$，高度为 $h_i$。不存在底面积相同的积木。比赛要求小朋友选择其中的 $k$ 块积木，一块一块地竖直叠放起来搭建成一座大厦。为了提高大厦的稳定性，要求放在下面的积木的底面积必须大于放在上面的积木的底面积。

如果相邻两块积木的高度差别太大，大厦的“层高”会显得参差不齐，影响大厦的美观度。定义大厦的“参差度”为整座大厦中相邻两块积木的高度差的绝对值之和。谁搭建的大厦的“参差度”最小，谁就获得比赛的胜利。

小 M 是个聪明的小朋友，她很快想出了搭建大厦的最优方案。

你知道她如何搭建大厦吗？你只需要输出小 M 搭建出的大厦的最小“参差度”。

【输入格式】

第一行包含两个整数 $n, k$

接下来 $n$ 行，每行包含两个整数 $s_i, h_i$

【输出格式】

一行，包含一个整数，表示答案。

【样例输入】

4 3
1 1
2 6
5 4
4 5

【样例输出】

2 

【数据范围】

30%的数据，$1 ≤ n ≤ 20$

100%的数据，$1 ≤ n ≤ 100, 1 ≤ k ≤ n, 1 ≤ s_i, h_i ≤ 200$