#1949. [noi省选联考 2020 A 卷] 魔法商店

[noi省选联考 2020 A 卷] 魔法商店

题目描述

笠笠和伦伦来到了一家魔法商店,这家商店内有 nn 件礼品,礼品从 1n1 \sim n 编号,ii 号礼品的魅力值为 cic_i,价格为 viv_i

两人希望购买一些礼品,但他们的要求比较奇怪:假设购买到的礼品集合为 S={s1,s2,,sp}(1sin)S=\{s_1,s_2,\dots,s_p\}(1\leq s_i\leq n),两人要求对于 SS 中任意的非空子集 T={t1,t2,,tq}T=\{t_1,t_2,\dots,t_q\},它包含的所有礼品的魅力值异或和都不为零,即:$c_{t_1} \oplus c_{t_2} \oplus \cdots \oplus c_{t_q} \neq 0$。其中 \oplus 是异或运算。在此基础上,两人还要求购买到的礼品数尽可能多。

例如:c1=1,c2=2,c3=5,c4=6,c5=7c_1=1,c_2=2,c_3=5,c_4=6,c_5=7。则 S1={2,3,5}S_1=\{2,3,5\} 不符合要求,因为 c2c3c5=0c_2 \oplus c_3 \oplus c_5=0S2={1,2,3}S_2=\{1,2,3\}S3={2,4,5}S_3=\{2,4,5\} 符合要求,其任意非空子集的异或和都不为零。S4={1,2}S_4=\{1,2\} 因为其包含的礼品数不是最多的。

满足两人要求的礼品集合可能很多,因此商店老板为两人挑选出了两个符合要求的礼品集合 AABB(显然它们所含的礼品数相同),伦伦喜欢集合 AA,但笠笠更喜欢集合 BB。为了笠笠同意购买集合 AA,伦伦决定使用魔法改变礼品价格。更具体地,伦伦能花费 (xvi)2(x-v_i)^2 的魔力值,将 ii 号礼品的价格改为任意整数 xx,每件礼品只能被改价一次。

伦伦希望改价后 AA 是所有符合要求的礼品集合之中价格总和最小的,且 BB 是所有符合要求的礼品集合之中价格总和最大的(一个礼品集合的价格总和为它包含的所有礼品的价格之和)。现在请你帮伦伦计算,他至少要花费多少魔力值才能完成他的目标。

输入格式

第一行两个整数 n,mn, m,分别表示总礼品数与礼品集合 A(B)A(B) 包含的礼品数。

第二行 nn 个整数 cic_i,第 ii 个整数表示 ii 号礼品的魅力值。

第三行 nn 个整数 viv_i,第 ii 个整数表示 ii 号礼品的价格。

第四行 mm 个整数 aia_i,表示礼品集合 AA 包含的礼品的编号。数据保证 aia_i 两两不同。

第五行 mm 个整数 bib_i,表示礼品集合 BB 包含的礼品的编号。数据保证 bib_i 两两不同。

数据保证 1ai,bin1 \leq a_i, b_i \leq n,且礼品集合 AABB 均符合两人的要求。

输出格式

仅一行一个整数,表示伦伦至少需要花费的魔力值。

样例

5 3
1 2 5 6 7
4 4 2 1 3
1 2 3
2 4 5
6

说明

样例 1 解释

符合条件的礼品集合有:$\{1,2,3\},\{1,2,4\},\{1,2,5\},\{1,3,4\},\{1,3,5\},\{2,3,4\},\{2,4,5\},\{3,4,5\}$。

一个最优的改价方案为:c1=c2=c4=c5=3c_1=c_2=c_4=c_5=3c3=2c_3=2

样例 2

见附加文件中 shop2.inshop2.ans

样例 3

见附加文件中 shop3.inshop3.ans

数据范围

对于所有测试数据:1n10001\leq n\leq 10001m641\leq m\leq 641ci<2641≤ c_i<2^{64}0vi1060\leq v_i\leq 10^6

每个测试点的具体限制见下表:

测试点编号 nn \leq mm \leq 特殊限制
131 \sim 3 1010 44 1vi51 \leq v_i \leq 5
464 \sim 6 5050 22 1vi101 \leq v_i \leq 10
7107 \sim 10 500500 3030 0vi10 \leq v_i \leq 1
111211 \sim 12 10001000 6464 AABB 相同
132013 \sim 20