QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100
[0]

# 6158. 魔法商店

Statistics

笠笠和伦伦来到了一家魔法商店,这家商店内有 n 件礼品,礼品从 1n 编号,i 号礼品的魅力值为 ci,价格为 vi

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

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

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

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

输入格式

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

第二行 n 个整数 ci,第 i 个整数表示 i 号礼品的魅力值。

第三行 n 个整数 vi,第 i 个整数表示 i 号礼品的价格。

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

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

数据保证 1ai,bin,且礼品集合 AB 均符合两人的要求。

输出格式

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

样例数据

样例 1 输入

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

样例 1 输出

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=3c3=2

样例 2

见下发文件。

样例 3

见下发文件。

子任务

对于所有测试数据:1n10001m641ci<2640vi106

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

测试点编号 n m 特殊限制
13 10 4 1vi5
46 50 2 1vi10
710 500 30 0vi1
1112 1000 64 AB 相同
1320