Description

数字图像中的像素可以用三个范围在 $0$ 到 $255$ 之间的整数表示，分别表示红、绿、蓝三种颜色的强度。为了压缩图像或创造艺术效果，许多照片编辑工具包括一个 posterize 操作，其工作原理如下。每个颜色通道单独检查；这个问题只关注红色通道。对于红色通道，posterized 图像最多允许 $k$ 个整数，而不是允许从 $0$ 到 $255$ 的所有整数。每个像素的原始红色强度被替换为允许整数中最接近的一个。照片编辑工具选择一组 $k$ 个整数，以最小化原始图像中所有像素引入的平方误差之和。如果有 $n$ 个像素的原始红色值为 $r_{1}, \ldots, r_{n}$，并且有 $k$ 个允许的整数 $v_{1}, \ldots, v_{k}$，则平方误差之和定义为

$$\sum\limits_{i=1}^n \min\limits_{1 \le j \le k}(r_i-v_j)^2$$

你的任务是计算在给定参数 $k$ 和图像像素红色强度描述的情况下，可以实现的最小平方误差之和。

Input Format

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

Output Format

显示为优化选择的 $k$ 个允许整数值的平方误差之和。

2 1
50 20000
150 10000

66670000

2 2
50 20000
150 10000

0

4 2
0 30000
25 30000
50 30000
255 30000

37500000

Hint

时间限制：2 秒，内存限制：512 MB。

题面翻译由 ChatGPT-4o 提供。