#6475. 「ICPC World Finals 2017」色调分离 Posterize

内存限制:1024 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tangjz

题目描述

数字图像的像素可以用三个在 0 255 之间的整数表示,它们分别表示红色、绿色和蓝色的强度。为了压缩图片或是为了产生艺术效果,许多图像编辑工具收录了如下所述的“色调分离”操作。每个颜色通道会分别考虑,本题只考虑红色通道的情况。不同于在红色通道使用 0 255 之间全部的整数,一张色调分离后的图片只会使用这些数字里至多 k 种整数。每个像素原来的红色强度会被替换成最相近的可用强度。图像编辑工具会选择 k 个整数来最小化替换过程引起的平方误差之和。假设原图有 n 个像素,它们的红色取值是 r_1 , \cdots , r_n ,而 k 种可用整数为 v_1 , \cdots , v_k ,那么平方误差之和被定义为

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

你的任务是计算可以实现的最小平方误差之和,参数 k 和图片的红色强度会给出。

输入格式

第一行包含两个整数 d (1 \leq d \leq 256) k (1 \leq k \leq d) ,分别表示原图中不同的红色强度有多少种,色调分离后可以使用的红色强度有多少种。

接下来 d 行描述了每种红色强度在原图中占据的像素点数量。每行包含两个整数 r (0 \leq r \leq 255) p (1 \leq p \leq 2^{26}) ,这里 r 是一种红色强度的取值,而 p 是这种取值对应的像素点数量。这 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