{"raw_statement":[{"iden":"background","content":"原题链接：<https://oier.team/problems/X1C>。"},{"iden":"statement","content":"给出一个长度为 $n$ 的序列 $a$。定义其前缀和数组 $b_i=\\sum_{j=1}^ia_j$。定义其权值 $S=\\sum_{i=1}^n(b_i\\bmod 2)$。\n\n你可以对序列 $a$ 进行若干次如下操作：\n\n* 交换 $a_i,a_j$，花费 $c_i+c_j$ 元，其中 $c$ 为给定序列；\n\n对于 $i=0\\sim n$，求使得 $S=i$ 的最少钱数。如果不可能，输出 $-1$。"},{"iden":"input","content":"**本题包含多组测试数据。**\n\n第一行一个正整数 $T$，表示测试数据组数。\n\n对于每组测试数据：\n\n第一行一个正整数 $n$，表示序列长度。\n\n第二行 $n$ 个正整数，表示序列 $a$。\n\n第三行 $n$ 个正整数，表示序列 $c$。"},{"iden":"output","content":"对于每组测试数据：\n\n一行，$n+1$ 个整数，第 $i$ 个表示 $S=i-1$ 的最少钱数。如果不可能，输出 $-1$。"},{"iden":"note","content":"**【样例解释】**\n\n对于第一组数据，初始 $\\sum_{i=1}^n(b_i\\bmod 2)=2$，故使 $S=2$ 最少要花 $0$ 元。\n\n交换 $a_1,a_2$ 即可使 $\\sum_{i=1}^n(b_i\\bmod 2)=1$，故使 $S=1$ 可以花费 $2$ 元。可以证明这是最优解。\n\n可以证明不存在交换方案使得 $S=0$ 或 $S=3$。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | 分值 | $n\\leq$ | $\\sum n\\leq$ | 特殊性质 |\n|:--:|:--:|:--:|:--:|:--:|\n| $1$ | $10$ | $5$ | $50$ | 无 |\n| $2$ | $10$ | $500$ | $500$ | $a$ 中至多有 $3$ 个奇数 |\n| $3$ | $15$ | $30$ | $150$ | 无 |\n| $4$ | $25$ | $100$ | $500$ | 无 |\n| $5$ | $10$ | $500$ | $500$ | $c_i=1$ |\n| $6$ | $30$ | $500$ | $500$ | 无 |\n\n对于 $100\\%$ 的数据：$1\\leq n,\\sum n\\leq500$，$1\\leq a_i\\leq10^9$，$1\\leq c_i\\leq10^6$，$1\\leq T\\leq500$。"}],"translated_statement":null,"sample_group":[["3\n3\n1 2 3\n1 1 1\n5\n1 2 3 4 5\n2 5 3 6 4\n10\n1 8 3 5 2 6 3 4 6 2\n3 2 7 1 8 2 5 8 3 1","-1 2 0 -1\n-1 -1 7 0 9 -1\n-1 -1 5 3 4 0 7 8 6 -1 -1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}