题目背景

[火箭][头盔][毛毛虫][奶龙][滑板].jpg

题目描述

小 H 有两个长度为 $n$ 的非负整数序列 $a_1, \ldots, a_n$ 与 $b_1, \ldots, b_n$。

他可以进行若干次操作：

• 选择一个整数 $x\in[1,n]$ 与一个正整数 $y$。
• 进行操作 $\forall i\in[1,x],a_i\gets a_i\oplus y$。即将 $[1,x]$ 中数异或上 $y$。
• 这次操作的代价为 $b_x$。

小 H 想通过若干次操作使得 $a$ 变为不下降序列，你需要帮他最小化代价的和。

输入格式

本题输入包含多组数据。

第一行，一个整数 $T$，表示数据组数。对于每组数据：

• 第一行，一个整数 $n$。
• 第二行，$n$ 个整数 $a_1, \ldots, a_n$。
• 第三行，$n$ 个整数 $b_1, \ldots, b_n$。

输出格式

对于每组数据，输出一行一个数，表示答案。

5
3
1 2 3
1 1 1
4
1 3 2 4
1 2 3 4
5
8 9 4 2 5
1 2 2 1 2
8
1 8 7 4 2 5 3 6
1 4 2 3 5 4 2 3
10
128 983 238 123 823 723 91 324 12 747
13 23 12 52 23 12 42 82 21 34

0
2
3
11
111

提示

【样例解释】

对于第一组数据，$a$ 本来就是不下降序列，不需要操作，故答案为 $0$。

对于第二组数据，选择 $x=2,y=1$ 操作，代价为 $b_2=2$。操作后 $a=[0,2,2,4]$，符合条件，故答案为 $2$。

对于第三组数据，操作两次：

• 选择 $x=4,y=28$，代价为 $b_4=1$，操作后序列变为 $a=[20,21,24,30,5]$。
• 选择 $x=5,y=16$，代价为 $b_5=2$，操作后序列变为 $a=[4,5,8,14,21 ]$。

故答案为 $1+2=3$。

【数据范围】

本题采用捆绑测试。

对于所有数据，保证 $1\le T,n,\sum n\le 5000$，$0\le a_i<2^{13}$，$1\le b_i\le 10^9$。

各子任务特殊限制如下：

子任务编号	$\sum n\le$	$a_i<$	特殊性质	分值
$1$	$5000$	$16$	A	$5$
$2$	$50$	$64$	B	$15$
$3$			无
$4$	$500$	$2^9$		$10$
$5$		$2^{13}$		$20$
$6$	$5000$	$2^9$		$10$
$7$		$2^{13}$		$25$

• 特殊性质 A：保证 $n\le 3$。
• 特殊性质 B：保证存在一种最优解，使得操作后的 $a$ 有 $a_n<64$。