{"problem":{"name":"[LSOT-2] 胜者组","description":{"content":"小 H 的学校在 noip 结束后要决定踢出一些学生回去学文化课。 具体的，学校一共有 $n$ 个同学，留下了最多 $m$ 个学习信息学的名额。 学校里的同学组成了 $k$ 个小团体，其中第 $i$ 个同学属于第 $c_i$ 个小团体。 你每次可以钦定两个处于同一小团体的学生学习文化课。若你让学生 $i,j(c_i=c_j)$ 去学习文化课，学生会产生 $a_i+a_j+x\\times|i-","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10156"},"statements":[{"statement_type":"Markdown","content":"小 H 的学校在 noip 结束后要决定踢出一些学生回去学文化课。\n\n具体的，学校一共有 $n$ 个同学，留下了最多 $m$ 个学习信息学的名额。\n\n学校里的同学组成了 $k$ 个小团体，其中第 $i$ 个同学属于第 $c_i$ 个小团体。\n\n你每次可以钦定两个处于同一小团体的学生学习文化课。若你让学生 $i,j(c_i=c_j)$ 去学习文化课，学生会产生 $a_i+a_j+x\\times|i-j|$ 的不满意度。这里 $x$ 是输入一开始给定的常数。\n\n你需要让学生的不满意度最小化，或报告无法留下不多于 $m$ 个学习信息学的学生。\n\n## Input\n\n第一行四个正整数 $n,m,k,x$。\n\n接下来两行每行 $n$ 个整数分别表示 $a_i,c_i$。\n\n## Output\n\n一行一个整数表示最小的不满意度。或输出 `Impossible` 表示无解。\n\n[samples]\n\n## Background\n\n进入胜者组就算胜利吗...\n\n至少人们都这样说。\n\n## Note\n\n样例解释：\n\n分别钦定 $(1,2)$ 和 $(4,6)$ 学习文化课，不满意度为 $(2+5+3\\times|1-2|)+(2+7+3\\times|4-6|)=25$。\n\n需要注意的是，一个同学不可以被钦定多次。\n\n**「本题采用捆绑测试」**\n\n- $\\texttt{Subtask 1(15pts)：}n\\le20$。\n- $\\texttt{Subtask 2(15pts)：}x=0$。\n- $\\texttt{Subtask 3(15pts)：}k=1$。\n- $\\texttt{Subtask 4(20pts)：}n\\le 300$。\n- $\\texttt{Subtask 5(35pts)：}$无特殊性质。\n\n对于全部的数据，$0\\le a_i,x\\le10^5$，$1\\le c_i\\le k\\le n\\le 5000$，$0\\le m\\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10156","tags":["动态规划 DP","背包 DP"],"sample_group":[["6 2 2 3\n2 5 7 2 5 7\n1 1 2 1 2 1","25"]],"created_at":"2026-03-03 11:09:25"}}