题目背景

233zhang 和他的同学们走在大街上，该街道可视为一条无限长直线。他们 各自分散在大街的各个角落，每个人的位置记作 $a_i$（$a_i$ 是整数，并且不保证唯 一）。现在他们需要汇合，你可以给出 $k$ 个汇合点，同学们可以前往任意一个 汇合点。汇合点位置可以安排在任意整数位置上。 同学们自然是想要偷懒的，他们会选择离自己位置最近的。由于每个人的体 质不同，同学们对于距离各自有不同的不满度系数，记作 $b_i$。对于每个人，他 的不满度计算为 $(a_i - x)^2$ $·$ $b_i$（其中 $x$ 为距离 $a_i$ 最近的汇合点的位置）。 为避免同学们因汇合点设置不合理而愤怒，你需要尽可能的使同学们的不满 度总和最小，并给出答案

题目描述

【题目描述】

233zhang 和他的同学们走在大街上，该街道可视为一条无限长直线。他们 各自分散在大街的各个角落，每个人的位置记作 $a_i$（$a_i$ 是整数，并且不保证唯 一）。现在他们需要汇合，你可以给出 $k$ 个汇合点，同学们可以前往任意一个 汇合点。汇合点位置可以安排在任意整数位置上。 同学们自然是想要偷懒的，他们会选择离自己位置最近的。由于每个人的体 质不同，同学们对于距离各自有不同的不满度系数，记作 $b_i$。对于每个人，他 的不满度计算为 $(a_i - x)^2$ $·$ $b_i$（其中 $x$ 为距离 $a_i$ 最近的汇合点的位置）。 为避免同学们因汇合点设置不合理而愤怒，你需要尽可能的使同学们的不满 度总和最小，并给出答案

输入格式

第一行输入两个数：$n$ $(1 ≤ n ≤ 200)$ 、$k$ $(1 ≤ k ≤ n)$ ，$n$ 是给定大街上的人 数，$k$ 是你确定的汇合点最多数量。 接下来有 $n$ 行，第 $i$ 行有两个整数 $a_i$ $(0 ≤ a_i ≤ 200)$ 和 $b_i$ $(1 ≤ b_i ≤ 10^9 )$， $a_i$ 代表该人所处位置，$b_i$ 代表他对于距离的不满度系数。

输出格式

一个整数，代表所有同学的不满度和的最小值。

输入输出样例 #1

输入 #1

2 1
3 3
10 2

输出 #1

59

输入输出样例 #2

输入 #2

2 2
50 200
150 300

输出 #2

0

输入输出样例 #3

输入 #3

5 2
0 3000
25 256
50 114514
150 65536
100 40000

输出 #3

69563466