\includegraphics[width=0.95\textwidth ]{RushmoreOpt2}

Pixels in a digital picture can be represented with three integers in the range $0$ to $255$ that indicate the intensity of the red, green, and blue colors. To compress an image or to create an artistic effect, many photo-editing tools include a “posterize” operation which works as follows. Each color channel is examined separately; this problem focuses only on the red channel. Rather than allow all integers from $0$ to $255$ for the red channel, a posterized image allows at most $k$ integers from this range. Each pixel’s original red intensity is replaced with the nearest of the allowed integers. The photo-editing tool selects a set of $k$ integers that minimizes the sum of the squared errors introduced across all pixels in the original image. If there are $n$ pixels that have original red values $r_1, \ldots , r_ n$, and $k$ allowed integers $v_1, \ldots , v_ k$, the sum of squared errors is defined as

\[ \sum _{i=1}^ n \min _{1 \leq j \leq k} (r_ i - v_ j)^2. \]

Your task is to compute the minimum achievable sum of squared errors, given parameter $k$ and a description of the red intensities of an image’s pixels.


The first line of the input contains two integers $d$ ($1 \leq d \leq 256$), the number of distinct red values that occur in the original image, and $k$ ($1 \leq k \leq d$), the number of distinct red values allowed in the posterized image. The remaining $d$ lines indicate the number of pixels of the image having various red values. Each such line contains two integers $r$ ($0 \leq r \leq 255$) and $p$ ($1 \leq p \leq 2^{26}$), where $r$ is a red intensity value and $p$ is the number of pixels having red intensity $r$. Those $d$ lines are given in increasing order of red value.


Display the sum of the squared errors for an optimally chosen set of $k$ allowed integer values.

Sample Input 1 Sample Output 1
2 1
50 20000
150 10000
Sample Input 2 Sample Output 2
2 2
50 20000
150 10000
Sample Input 3 Sample Output 3
4 2
0 30000
25 30000
50 30000
255 30000
CPU Time limit 2 seconds
Memory limit 1024 MB
Difficulty 3medium
Statistics Show
License Restricted, used with permission

Please log in to submit a solution to this problem

Log in