题目背景

进入胜者组就算胜利吗...

至少人们都这样说。

题目描述

小 H 的学校在 noip 结束后要决定踢出一些学生回去学文化课。

具体的，学校一共有 $n$ 个同学，留下了最多 $m$ 个学习信息学的名额。

学校里的同学组成了 $k$ 个小团体，其中第 $i$ 个同学属于第 $c_i$ 个小团体。

你每次可以钦定两个处于同一小团体的学生学习文化课。若你让学生 $i,j(c_i=c_j)$ 去学习文化课，学生会产生 $a_i+a_j+x\times|i-j|$ 的不满意度。这里 $x$ 是输入一开始给定的常数。

你需要让学生的不满意度最小化，或报告无法留下不多于 $m$ 个学习信息学的学生。

输入格式

第一行四个正整数 $n,m,k,x$。

接下来两行每行 $n$ 个整数分别表示 $a_i,c_i$。

输出格式

一行一个整数表示最小的不满意度。或输出 Impossible 表示无解。

6 2 2 3
2 5 7 2 5 7
1 1 2 1 2 1

25

提示

样例解释：

分别钦定 $(1,2)$ 和 $(4,6)$ 学习文化课，不满意度为 $(2+5+3\times|1-2|)+(2+7+3\times|4-6|)=25$。

需要注意的是，一个同学不可以被钦定多次。

「本题采用捆绑测试」

• $\texttt{Subtask 1(15pts)：}n\le20$。
• $\texttt{Subtask 2(15pts)：}x=0$。
• $\texttt{Subtask 3(15pts)：}k=1$。
• $\texttt{Subtask 4(20pts)：}n\le 300$。
• $\texttt{Subtask 5(35pts)：}$无特殊性质。

对于全部的数据，$0\le a_i,x\le10^5$，$1\le c_i\le k\le n\le 5000$，$0\le m\le n$。