数字图像中的像素可以用 0 到 255 之间的三个整数表示，分别代表红、绿、蓝三种颜色的强度。为了压缩图像或产生艺术效果，许多照片编辑工具都包含一种“色调分离”（posterize）操作，其工作原理如下：每个颜色通道被单独处理；本题仅关注红色通道。色调分离后的图像不再允许红色通道使用 0 到 255 之间的所有整数，而是最多允许使用该范围内的 $k$ 个整数。每个像素原始的红色强度会被替换为允许的整数中最接近的一个。照片编辑工具会选择一组 $k$ 个整数，使得原始图像中所有像素产生的平方误差之和最小。如果有 $n$ 个像素，其原始红色值为 $r_1, \dots, r_n$，且允许的 $k$ 个整数为 $v_1, \dots, v_k$，则平方误差之和定义为：

$$\sum_{i=1}^{n} \min_{1 \le j \le k} (r_i - v_j)^2$$

你的任务是给定参数 $k$ 以及图像像素红色强度的描述，计算出所能达到的最小平方误差之和。

输入格式

输入的第一行包含两个整数 $d$ ($1 \le d \le 256$)，即原始图像中出现的不同红色值的数量，以及 $k$ ($1 \le k \le d$)，即色调分离后的图像中允许的不同红色值的数量。 接下来的 $d$ 行表示图像中具有不同红色值的像素数量。每行包含两个整数 $r$ ($0 \le r \le 255$) 和 $p$ ($1 \le p \le 2^{26}$)，其中 $r$ 是红色强度值，$p$ 是具有红色强度 $r$ 的像素数量。这 $d$ 行按红色值递增的顺序给出。

输出格式

输出最优选择 $k$ 个允许的整数值后所能达到的最小平方误差之和。

样例

样例输入 1

2 1
50 20000
150 10000

样例输出 1

66670000

样例输入 2

2 2
50 20000
150 10000

样例输出 2

0

样例输入 3

4 2
0 30000
25 30000
50 30000
255 30000

样例输出 3

37500000

Figure 1. 原始图像与色调分离后的图像对比