Problem Description

Given \( d \) classes of elements, where the \( i \)-th class has a value \( r_i \) and \( p_i \) elements, these elements can be arranged in a sequence of length \( n = \sum p_i \). Your task is to plan a sequence of length \( k \) such that the following defined sequence error is minimized:

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

Find the minimum sequence error.

Constraints: \( 1 \le k \le d \le 256 \), \( 0 \le r \le 255 \), \( 1 \le p \le 2^{26} \).

Input Format

The first line of the input contains two integers \( d \) ( \( 1 \le d \le 256 \) ), the number of distinct red values in the original image, and \( k \) ( \( 1 \le k \le d \) ), the number of distinct red values allowed in the posterized image. The next \( d \) lines each contain 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 with red intensity \( r \). These \( d \) lines are sorted in increasing order of red value.

Output Format

Output the sum of the squared errors for an optimally chosen set of \( k \) allowed integer values.

Sample Input and Output

Input Sample #1

2 1
50 20000
150 10000

Output Sample #1

66670000

Input Sample #2

2 2
50 20000
150 10000

Output Sample #2

0

Input Sample #3

4 2
0 30000
25 30000
50 30000
255 30000

Output Sample #3

37500000

Notes/Hints

Time limit: 2 seconds, Memory limit: 512 MB.

见题面 Input 部分

见题面 Output 部分