U455627 XJB的促销活动

$F$ 超市职员 $xjb$ 作为一位资深的铁公鸡，身上总有个询价表以方便他追求性价比，我们可以把询价表看做一个有 $n$ 个物品的集合 $A$，正整数 $a_i$ 表示物品 $i$ 的美丽程度，相似度 $b_i = a_i \bmod 2$。\ 一天，$F$ 超市进行了一场促销活动，不过由于老板的看重，促销活动落到了 $xjb$ 的身上，为了赚钱 $xjb$ 打算偷偷进行若干次的操作： + 对于任意 $1 \le l < r \le n$ ，若 $b_l = 1$，$b_r = 0$，则将 $a_l \leftarrow a_l - 1$，$a_r \leftarrow a_r + 1$。 + 对于任意 $1 \le l < r \le n$ ，若 $b_l = 0$，$b_r = 1$，则将 $a_l \leftarrow a_l + 1$，$a_r \leftarrow a_r - 1$。 由于 $xjb$ 擅自改动活动方式，老板打算降低 $xjb$ 的工资。对于每次操作，花费 $c_l + c_{r+1}$，$xjb$ 作为贪得无厌的奸商，自然希望自己的工资更高，但这 $n$ 个物品有个特性，那就是想要买下第 $i$ 件物品，需保证 $(\sum_{j=1}^i a_j) \equiv1\pmod{2}$。 现在有 $m$ 次询问，每次询问一个数 $x$，求当购买的物品数量为 $x$ 时的最小花费数。由于 $xjb$ 忙于刷题，所以这项任务交给了你。**每件物品最多促销一次。**

通俗地讲，给定序列 $a_i$，$c_i$，$b_i = a_i \bmod 2$。 两种操作，**对于任意 $a_i$ 至多进行一次操作**： + $a_l \leftarrow a_l - 1$，$a_r \leftarrow a_r + 1$，$(b_l = 1，b_r = 0)$，花费 $c_l + c_r$。 $(1 \le l < r \le n)$ + $a_l \leftarrow a_l + 1$，$a_r \leftarrow a_r - 1$，$(b_l = 0，b_r = 1)$，花费 $c_l + c_r$。 $(1 \le l < r \le n)$ $m$ 次询问，每次询问给出一个 $x$，问进行若干次操作后，是否存在 $$ \sum_{i=1}^n ((\sum_{j=1}^i a_j) \bmod 2) = x $$ 若存在，求此时的最小花费值，反之输出 $-1$。

第一行两个正整数 $n$，$m$，表示序列长度和询问数。 第二行 $n$ 个正整数，表示序列 $a$。 第三行 $n$ 个正整数，表示序列 $c$。 接下来 $m$ 行，每行一个正整数 $x$，表示一次询问。

共 $m$ 行，每行一个正整数，为最低花费数，若无法购买恰好 $x$ 个物品，输出 $-1$。

### 样例$1$解释： 对于询问 $2$，将 $a_1 \leftarrow a_1 + 1$，$a_4 \leftarrow a_4 - 1$，$(b_1 = 0，b_4 = 1)$。序列变为 $3,1,4,4,3$，总价值为 $2$，此时为最小花费 $2$。 对于询问 $3$，取 $l = 1$，$r = 2$ 时花费最小，为 $2 $。 对于询问 $1$，可证得没有可行方案。 ### 数据范围： 对于 $30\%$ 的数据，$1 \le m \le n \le 500$。 对于 $100\%$ 的数据，$1 \le m \le n \le 5 \times 10^3$，$1 \le a_i,c_i \le 10^9$，$1 \le x \le n$。