Minimizing Student Dissatisfaction

After the NOIP contest, Little H’s school must decide to send some students back to take cultural courses. In the school there are $n$ students, and at most $m$ of them can remain to study information technology. The students form $k$ different groups (for $i=1,2,\dots,n$, student $i$ belongs to group $c_i$).

You are allowed to choose two students from the same group and send both of them to study cultural courses. If you choose students $i$ and $j$ (with $c_i=c_j$) for cultural courses, they will incur a dissatisfaction of $$a_i+a_j+x\times|i-j|$$ (where $x$ is a constant given at the beginning of the input).

Your task is to force exactly $n-m$ students (note that as you always send them in pairs, $n-m$ must be even) to take cultural courses (so that at most $m$ students remain in information technology), while minimizing the total dissatisfaction. If it is impossible to achieve this, output -1.

Note: You must form pairs from within the same group. Each student can be used in at most one pair.

inputFormat

The first line contains three integers $n$, $m$, and $x$.

The second line contains $n$ integers: $a_1,a_2,\dots,a_n$.

The third line contains $n$ integers: $c_1,c_2,\dots,c_n$, where $c_i$ is the group number of the $i$-th student.

outputFormat

Output a single integer — the minimum total dissatisfaction if it is possible to send students in pairs so that at most $m$ students remain in information technology. Otherwise, output -1.

sample

4 2 1
1 2 3 4
1 1 2 2

4