#3301. 「联合省选 2020 A」魔法商店

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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

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

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

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

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

输入格式

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

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

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

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

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

数据保证 1\le a_i, b_i \le n ,且礼品集合 A B 均符合两人的要求。

输出格式

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

样例

样例输入 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\}

一个最优的改价方案为: c_1 = c_2 = c_4 = c_5 = 3,c_3 = 2

样例 2

见附加文件中 shop2.inshop2.ans

样例 3

见附加文件中 shop3.inshop3.ans

数据范围与提示

对于所有测试数据: 1\le n\le 1000 1\le m\le 64 1\le c_i < 2^{64} 0\le v_i\le 10^6

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

测试点编号 n\le m\le 特殊限制
1\sim 3 10 4 1\le v_i\le 5
4\sim 6 50 2 1\le v_i\le 10
7\sim 10 500 30 0\le v_i\le 1
11\sim 12 1000 64 A B 相同
13\sim 20