该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

汉明距离：两个长度相同的字符串对应位置上字符不相同的数量。例如，字符串 $S='1011010'$，$T='1010110'$，其中 $S$ 和 $T$ 的第 $4,5$ 个位置的字符不相同，则 $S$ 和 $T$ 的汉明距离为 $2$。

给定两个长度均为 $n$ 的二进制序列 $S$ 和 $T$。你可以改变 $S$ 中任意位置的数字：如果该位置是 $0$，将其变为 $1$；如果该位置是 $1$，将其变为 $0$。改变 $S$ 中第 $i$ 位数字的代价为 $C_i$。请你通过改变 $S$ 中若干位置的数字，使得 $S$ 和 $T$ 的汉明距离恰好为 $K$，并计算所需的最小总代价。

例如：$n=5$，$S='10010'$，$T='01111'$；改变 $S$ 的每一位的代价分别为 $1,4,9,8,5$；$K=1$。初始时 $S$ 和 $T$ 的汉明距离为 $4$（第 $1,2,3,5$ 位数字均不相同）。要使得 $S$ 和 $T$ 的汉明距离变为 $1$，且总代价最小，可以选择改变 $S$ 的第 $1,2,5$ 位，总代价为 $10$（$1+4+5$）。

输入格式

第一行输入一个整数 $n$，表示二进制序列的长度。
第二行和第三行各输入一个仅由 $0$ 和 $1$ 组成的长度为 $n$ 的二进制序列，分别表示序列 $S$ 和序列 $T$。
第四行输入 $n$ 个整数 $C_i$，表示改变序列 $S$ 的第 $i$ 位的代价，整数之间以一个空格隔开。
第五行输入一个整数 $K$，表示目标汉明距离。

输出格式

输出一个整数，表示使得 $S$ 和 $T$ 的汉明距离恰好为 $K$ 时的最小总代价。

样例输入输出

样例输入1

5
10010
01111
1 4 9 8 5
1

样例输出1

10

数据范围与测试点说明

• $1\le n\le 1000$；
• 序列 $S,T$ 均为长度为 $n$ 的二进制串（仅包含 $0$ 和 $1$）；
• $1\le C_i\le 5000$；
• $0\le K\le n$。

时间限制与内存限制

• 时间限制：$1$ 秒
• 内存限制：$256$ MB