URI Online Judge | 2643
# Posterize

**Timelimit: 2**

By ACM-ICPC World Finals 2017 United States

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}** , . . . ,

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 ≤ **d** ≤ 256), the number of distinct red values that occurin the original image, and **k** (1 ≤ **k** ≤ **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 ≤ **r** ≤ 255) and **p** (1 ≤ **p** ≤ 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.

Input Samples | Output Samples |

2 1 |
66670000 |

2 2 |
0 |

4 2 |
37500000 |