# Posterize 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.

## Input

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.

## Output

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

66670000

Sample Input 2 Sample Output 2
2 2
50 20000
150 10000

0

Sample Input 3 Sample Output 3
4 2
0 30000
25 30000
50 30000
255 30000

37500000
{"ft_lang_label":"__label__en","ft_lang_prob":0.7838136,"math_prob":0.9990763,"size":2030,"snap":"2019-51-2020-05","text_gpt3_token_len":566,"char_repetition_ratio":0.13129319,"word_repetition_ratio":0.027027028,"special_character_ratio":0.31034482,"punctuation_ratio":0.0721393,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99932456,"pos_list":[0,1,2],"im_url_duplicate_count":[null,1,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-01-28T21:03:37Z\",\"WARC-Record-ID\":\"<urn:uuid:54f77522-001b-486c-8e75-b6d5e89a6f3a>\",\"Content-Length\":\"18999\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:0be8476a-a151-4f26-8375-c169177d4562>\",\"WARC-Concurrent-To\":\"<urn:uuid:55286e66-795a-4042-9afa-224ae22e5d30>\",\"WARC-IP-Address\":\"129.62.151.4\",\"WARC-Target-URI\":\"https://online.acmicpc.org/problems/posterize\",\"WARC-Payload-Digest\":\"sha1:YBJA2FCOFHQ2DHVZVFMVBTMA5OARTFOC\",\"WARC-Block-Digest\":\"sha1:YKOIIUVONHNXEBU7P77WEBPFL4YHDIK4\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-05/CC-MAIN-2020-05_segments_1579251783000.84_warc_CC-MAIN-20200128184745-20200128214745-00456.warc.gz\"}"}