← 返回题目列表

Codeforces · 2077/F

F. 与 x 或

中文机器翻译题面 查看原题

假设您有两个数组 $$$c$$$ 和 $$$d$$$,每个数组的长度为 $$$k$$$。 $$$(c, d)$$$ 被称为 好 如果通过执行以下操作任意多次可以将 $$$c$$$ 更改为 $$$d$$$。

  • 选择两个不同的索引 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq k$$$, $$$i \neq j$$$) 和一个非负整数 $$$x$$$ ($$$0 \leq x \lt 2^{30}$$$)。然后,应用以下转换:
    • $$$c_i := c_i \mathbin{\&} x$$$,其中 $$$\&$$$ 表示按位 AND 运算。
    • $$$c_j := c_j \mathbin{|} x$$$,其中 $$$|$$$ 表示按位或运算。

给定两个数组 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$,包含不超过 $$$m$$$ 的非负整数。

您可以对这些数组执行两种类型的移动任意次数:

  1. 选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 并设置 $$$a_i := a_i + 1$$$。
  2. 选择索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 并设置 $$$b_i := b_i + 1$$$。

请注意,在执行移动时,$$$a$$$ 和 $$$b$$$ 的元素可能会在某个时刻超过 $$$m$$$。

求使 $$$(a, b)$$$ 配对良好所需的最少移动次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^6$$$) - 数组 $$$a$$$ 和 $$$b$$$ 的长度,以及这些数组中的最大可能值。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq m$$$) — 表示数组 $$$a$$$。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i \leq m$$$) — 表示数组 $$$b$$$。

此外,保证所有测试用例中 $$$n$$$ 的所有值的总和以及 $$$m$$$ 的所有值的总和不超过 $$$2 \cdot 10^6$$$。

输出

对于每个测试用例,输出一个整数 - 使 $$$(a, b)$$$ 配对良好所需的最小移动次数。

示例

输入
复制

5
4 3
0 1 2 3
0 1 2 3
3 32
8 9 32
8 6 32
5 64
5 7 16 32 64
4 8 16 32 64
4 11
9 1 4 3
8 11 6 2
5 10
7 9 5 4 2
3 10 6 5 9

输出
复制

0
2
2
0
1

注意

在第一种情况下,我们已经有 $$$a = b$$$。

在第二种情况下,我们可以在索引 $$$i = 2$$$ 上执行两次移动 $$$2$$$ 。数组 $$$b$$$ 变为 $$$[8, 8, 32]$$$。我们可以看到 $$$(a, b)$$$ 现在很好。

在第三种情况下,我们可以对索引 $$$i = 1$$$ 执行 move $$$2$$$,然后对索引 $$$i = 2$$$ 执行 move $$$1$$$。可以证明,您无法在少于 $$$2$$$ 的移动中使 $$$(a, b)$$$ 成为良好的货币对。