포스터화

디지털 사진의 픽셀은 빨강, 초록, 파랑의 세기를 나타내는 0 이상 255 이하의 정수 세 개로 표현한다. 이미지를 압축하거나 독특한 느낌을 주려고 많은 사진 편집 도구에 포스터화(posterize) 기능이 들어 있다. 포스터화는 색 채널마다 따로 처리하며, 이 문제에서는 빨강 채널만 다룬다.

포스터화한 이미지의 빨강 채널은 0부터 255까지의 정수를 모두 쓰지 않고 그중 최대 $k$개만 쓴다. 각 픽셀의 원래 빨강 세기는 허용된 정수 중 가장 가까운 값으로 바뀐다. 편집 도구는 원본 이미지의 모든 픽셀에서 생기는 오차 제곱의 합이 최소가 되도록 정수 $k$개를 고른다. 픽셀 $n$개의 원래 빨강 값이 $r_1, \dots, r_n$이고 허용된 정수가 $v_1, \dots, v_k$일 때, 오차 제곱의 합은 다음과 같이 정의한다.

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

$k$와 이미지 픽셀의 빨강 세기 정보가 주어지면, 오차 제곱의 합이 가질 수 있는 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 원본 이미지에 나타나는 서로 다른 빨강 값의 개수 $d$ ($1 \le d \le 256$)와 포스터화한 이미지에서 허용하는 빨강 값의 개수 $k$ ($1 \le k \le d$)가 주어진다.

다음 $d$개 줄에는 빨강 세기 $r$ ($0 \le r \le 255$)와 세기가 $r$인 픽셀의 수 $p$ ($1 \le p \le 2^{26}$)가 공백으로 구분되어 주어진다. 이 $d$개 줄은 빨강 값이 증가하는 순서로 주어진다.

허용할 정수 $k$개를 가장 좋게 골랐을 때의 오차 제곱의 합을 출력한다.