Posterize

A pixel in a digital picture is represented by three integers from 0 to 255 that give the intensity of red, green, and blue. To compress an image or to create an artistic effect, many photo editing tools include a posterize operation. Each color channel is handled separately, and this problem deals only with the red channel.

The red channel of a posterized image does not use every integer from 0 to 255, only at most $k$ of them. The original red intensity of each pixel is replaced by the nearest allowed integer. The editing tool picks the $k$ integers so that the sum of the squared errors over all pixels of the original image is as small as possible. If the $n$ pixels have original red values $r_1, \dots, r_n$ and the allowed integers are $v_1, \dots, v_k$, the sum of squared errors is defined as

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

Given $k$ and the red intensities of the image's pixels, compute the minimum achievable sum of squared errors.

The first line contains the number of distinct red values that occur in the original image, $d$ ($1 \le d \le 256$), and the number of red values allowed in the posterized image, $k$ ($1 \le k \le d$).

Each of the next $d$ lines contains a red intensity $r$ ($0 \le r \le 255$) and the number of pixels whose red intensity is $r$, $p$ ($1 \le p \le 2^{26}$), separated by a space. Those $d$ lines are given in increasing order of red value.

Print the sum of the squared errors for an optimally chosen set of $k$ allowed integers.