【MX-X1-T3】「KDOI-05」简单的序列问题

给出一个长度为 $n$ 的序列 $a$。定义其前缀和数组 $b_i=\sum_{j=1}^ia_j$。定义其权值 $S=\sum_{i=1}^n(b_i\bmod 2)$。 你可以对序列 $a$ 进行若干次如下操作： * 交换 $a_i,a_j$，花费 $c_i+c_j$ 元，其中 $c$ 为给定序列； 对于 $i=0\sim n$，求使得 $S=i$ 的最少钱数。如果不可能，输出 $-1$。

**本题包含多组测试数据。** 第一行一个正整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行一个正整数 $n$，表示序列长度。 第二行 $n$ 个正整数，表示序列 $a$。 第三行 $n$ 个正整数，表示序列 $c$。

对于每组测试数据： 一行，$n+1$ 个整数，第 $i$ 个表示 $S=i-1$ 的最少钱数。如果不可能，输出 $-1$。

3
3
1 2 3
1 1 1
5
1 2 3 4 5
2 5 3 6 4
10
1 8 3 5 2 6 3 4 6 2
3 2 7 1 8 2 5 8 3 1

-1 2 0 -1
-1 -1 7 0 9 -1
-1 -1 5 3 4 0 7 8 6 -1 -1

**【样例解释】** 对于第一组数据，初始 $\sum_{i=1}^n(b_i\bmod 2)=2$，故使 $S=2$ 最少要花 $0$ 元。 交换 $a_1,a_2$ 即可使 $\sum_{i=1}^n(b_i\bmod 2)=1$，故使 $S=1$ 可以花费 $2$ 元。可以证明这是最优解。 可以证明不存在交换方案使得 $S=0$ 或 $S=3$。 **【数据范围】** **本题采用捆绑测试。** | 子任务编号 | 分值 | $n\leq$ | $\sum n\leq$ | 特殊性质 | |:--:|:--:|:--:|:--:|:--:| | $1$ | $10$ | $5$ | $50$ | 无 | | $2$ | $10$ | $500$ | $500$ | $a$ 中至多有 $3$ 个奇数 | | $3$ | $15$ | $30$ | $150$ | 无 | | $4$ | $25$ | $100$ | $500$ | 无 | | $5$ | $10$ | $500$ | $500$ | $c_i=1$ | | $6$ | $30$ | $500$ | $500$ | 无 | 对于 $100\%$ 的数据：$1\leq n,\sum n\leq500$，$1\leq a_i\leq10^9$，$1\leq c_i\leq10^6$，$1\leq T\leq500$。