Background

Does getting into the winners bracket count as winning...

At least, people say so.

Problem Description

After NOIP ends, Xiao H's school wants to decide to kick out some students and make them go back to regular classes.

Specifically, the school has $n$ students in total, and it keeps at most $m$ slots for studying informatics.

The students in the school form $k$ small groups. Student $i$ belongs to group $c_i$.

Each time, you may choose two students in the same group to attend regular classes. If you make students $i, j (c_i = c_j)$ attend regular classes, the students will produce dissatisfaction of $a_i + a_j + x \times |i - j|$. Here $x$ is a constant given at the beginning of the input.

You need to minimize the total dissatisfaction, or report that it is impossible to keep no more than $m$ students studying informatics.

Input Format

The first line contains four positive integers $n, m, k, x$.

The next two lines each contain $n$ integers, representing $a_i$ and $c_i$, respectively.

Output Format

Output one integer in one line, representing the minimum total dissatisfaction. Or output Impossible if there is no solution.

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

25

Hint

Sample explanation:

Choose $(1, 2)$ and $(4, 6)$ to attend regular classes. The dissatisfaction is $(2 + 5 + 3 \times |1 - 2|) + (2 + 7 + 3 \times |4 - 6|) = 25$.

Note that a student cannot be chosen more than once.

"This problem uses bundled testdata."

• $\texttt{Subtask 1(15pts):} n \le 20$.
• $\texttt{Subtask 2(15pts):} x = 0$.
• $\texttt{Subtask 3(15pts):} k = 1$.
• $\texttt{Subtask 4(20pts):} n \le 300$.
• $\texttt{Subtask 5(35pts):}$ no special properties.

Constraints: for all testdata, $0 \le a_i, x \le 10^5$, $1 \le c_i \le k \le n \le 5000$, $0 \le m \le n$.

Translated by ChatGPT 5