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 pho\(to-ed\)iting 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 pho\(to-ed\)iting 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}\), . . . , r_{n}, and \(k\) allowed integers \(v_{1}\), . . . , v_{k}, the sum of squared errors is defined as \(n\) X \(i=1\) min {1}{j}}_{k^{(}{i}{v}{)} 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 \le d \le 256\)), the number of distinct red values that occur in the original image, and \(k\) (\(1 \le k \le 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 \le r \le 255\)) and \(p\) (\(1 \le p \le 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.

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2017