{"problem":{"name":"[GXPC-S 2025] 队伍集结 / team","description":{"content":" 233zhang 和他的同学们走在大街上，该街道可视为一条无限长直线。他们各自分散在大街的各个角落，每个人的位置记作 $a_i$ （$a_i$ 是整数，并且不保证唯一）。现在他们需要汇合，你可以给出 $k$ 个汇合点，同学们可以前往任意一个汇合点。汇合点位置可以安排在任意整数位置上。 同学们自然是想要偷懒的，他们会选择离自己位置最近的。由于每个人的体质不同，同学们对于距离各自有不同的不满意系数","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB4373"},"statements":[{"statement_type":"Markdown","content":"233zhang 和他的同学们走在大街上，该街道可视为一条无限长直线。他们各自分散在大街的各个角落，每个人的位置记作 $a_i$ （$a_i$ 是整数，并且不保证唯一）。现在他们需要汇合，你可以给出 $k$ 个汇合点，同学们可以前往任意一个汇合点。汇合点位置可以安排在任意整数位置上。\n\n同学们自然是想要偷懒的，他们会选择离自己位置最近的。由于每个人的体质不同，同学们对于距离各自有不同的不满意系数，记作 $b_i$。对于每个人，他的不满意度计算为 $\n(a_i - x)^2 \\times b_i\n$（其中 $x$ 为距离 $a_i$ 最近的汇合点的位置）。\n\n为避免同学们因汇合点设置不合理而愤怒，你需要尽可能地使同学们的不满意度总和最小，并给出答案。\n\n## Input\n\n第一行输入两个数：$n$ $(1 \\le n \\le 200)$、$k$ $(1 \\le k \\le n)$，$n$ 是给定大街上的人数，$k$ 是你确定的汇合点最多数量。  \n接下来有 $n$ 行，第 $i$ 行有两个整数 $a_i$ $(0 \\le a_i \\le 200)$ 和 $b_i$ $(1 \\le b_i \\le 10^9)$，$a_i$ 代表该人所处位置，$b_i$ 代表他对于距离的不满意系数。\n\n## Output\n\n一个整数，代表所有同学的不满意度和的最小值。\n\n[samples]\n\n## Background\n\n题目来源：2025 年广西中小学生程序设计挑战赛复赛（进阶组[试题](https://mp.weixin.qq.com/s?__biz=MzI3NDM3MzcwNQ==&mid=2247490166&idx=5&sn=e7ba7e3bc8126027b9abd662518c208b&chksm=ea9c06dd4d18206ed9d88124cc78b947298df2555889e98620204c2ea1471f58c135c00f99fb&mpshare=1&scene=23&srcid=0724dNJdhMxpUHag1dqkhiqL&sharer_shareinfo=7e47197d6e5c044ae705613db988029c&sharer_shareinfo_first=7e47197d6e5c044ae705613db988029c#rd)）。\n\n## Note\n\n#### 样例解释\n- 样例 $1$ 中，我们选择将唯一的一个汇聚点放置在 6 上，此时第一个人他的不满意度为 $(3 - 6)^2 \\times 3 = 27$，第二个人他的不满意度为 $(10 - 6)^2 \\times 2 = 32$，故总不满意度为 $27 + 32 = 59$。此时为最优解。\n- 样例 $2$ 中，我们选择在 50、150 处分别建立汇聚点，第一个人会选择前往 50 位置的汇聚点，第二个人会前往 150 位置的汇聚点。此时总不满意度为 0。\n\n#### 数据范围  \n- 对于 10% 的数据，保证 $k = 1$，$0 \\le a_i \\le 20$，$1 \\le k \\le n \\le 20$。  \n- 对于 40% 的数据，保证 $0 \\le a_i \\le 20$，$1 \\le k \\le n \\le 20$。  \n- 对于 100% 的数据，保证 $0 \\le a_i \\le 200$，$1 \\le k \\le n \\le 200$，$1 \\le b_i \\le 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4373","tags":["动态规划 DP","2025","广西"],"sample_group":[["2 1\n3 3\n10 2","59"],["2 2\n50 200\n150 300","0"],["5 2\n0 3000\n25 256\n50 114514\n150 65536\n100 40000","69563466"]],"created_at":"2026-03-03 11:09:25"}}