#1949. [noi省选联考 2020 A 卷] 魔法商店
[noi省选联考 2020 A 卷] 魔法商店
题目描述
笠笠和伦伦来到了一家魔法商店,这家商店内有 件礼品,礼品从 编号, 号礼品的魅力值为 ,价格为 。
两人希望购买一些礼品,但他们的要求比较奇怪:假设购买到的礼品集合为 ,两人要求对于 中任意的非空子集 ,它包含的所有礼品的魅力值异或和都不为零,即:$c_{t_1} \oplus c_{t_2} \oplus \cdots \oplus c_{t_q} \neq 0$。其中 是异或运算。在此基础上,两人还要求购买到的礼品数尽可能多。
例如:。则 不符合要求,因为 。 与 符合要求,其任意非空子集的异或和都不为零。 因为其包含的礼品数不是最多的。
满足两人要求的礼品集合可能很多,因此商店老板为两人挑选出了两个符合要求的礼品集合 与 (显然它们所含的礼品数相同),伦伦喜欢集合 ,但笠笠更喜欢集合 。为了笠笠同意购买集合 ,伦伦决定使用魔法改变礼品价格。更具体地,伦伦能花费 的魔力值,将 号礼品的价格改为任意整数 ,每件礼品只能被改价一次。
伦伦希望改价后 是所有符合要求的礼品集合之中价格总和最小的,且 是所有符合要求的礼品集合之中价格总和最大的(一个礼品集合的价格总和为它包含的所有礼品的价格之和)。现在请你帮伦伦计算,他至少要花费多少魔力值才能完成他的目标。
输入格式
第一行两个整数 ,分别表示总礼品数与礼品集合 包含的礼品数。
第二行 个整数 ,第 个整数表示 号礼品的魅力值。
第三行 个整数 ,第 个整数表示 号礼品的价格。
第四行 个整数 ,表示礼品集合 包含的礼品的编号。数据保证 两两不同。
第五行 个整数 ,表示礼品集合 包含的礼品的编号。数据保证 两两不同。
数据保证 ,且礼品集合 和 均符合两人的要求。
输出格式
仅一行一个整数,表示伦伦至少需要花费的魔力值。
样例
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\}$。
一个最优的改价方案为:,。
样例 2
见附加文件中 shop2.in
与 shop2.ans
。
样例 3
见附加文件中 shop3.in
与 shop3.ans
。
数据范围
对于所有测试数据:,,,。
每个测试点的具体限制见下表:
测试点编号 | 特殊限制 | ||
---|---|---|---|
与 相同 | |||
无 |