310767: CF1883G1. Dances (Easy version)

G1. Dances (Easy version)time limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the easy version of the problem. The only difference is that in this version $m = 1$.

You are given two arrays of integers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$. Before applying any operations, you can reorder the elements of each array as you wish. Then, in one operation, you will perform both of the following actions, if the arrays are not empty:

• Choose any element from array $a$ and remove it (all remaining elements are shifted to a new array $a$),
• Choose any element from array $b$ and remove it (all remaining elements are shifted to a new array $b$).

Let $k$ be the final size of both arrays. You need to find the minimum number of operations required to satisfy $a_i < b_i$ for all $1 \leq i \leq k$.

This problem was too easy, so the problem author decided to make it more challenging. You are also given a positive integer $m$. Now, you need to find the sum of answers to the problem for $m$ pairs of arrays $(c[i], b)$, where $1 \leq i \leq m$. Array $c[i]$ is obtained from $a$ as follows:

• $c[i]_1 = i$,
• $c[i]_j = a_j$, for $2 \leq j \leq n$.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) - the number of sets of input data. This is followed by their description.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^5$, $m = 1$) - the size of arrays $a$ and $b$ and the constraints on the value of element $a_1$.

The second line of each test case contains $n - 1$ integers $a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$).

The third line of each test case contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output the total number of minimum operations for all pairs of arrays $(c_i, b)$.

ExampleInput

4
2 1
1
3 2
4 1
5 1 5
3 8 3 3
8 1
4 3 3 2 2 1 1
1 1 1 1 3 3 3 3
9 1
9 2 8 3 7 4 6 5
1 2 3 2 1 4 5 6 5

Output

0
1
4
4

Note

In the first test case for the pair of arrays $([1, 1], [3, 2])$, the answer is $0$. No operations or reordering of elements are needed.

题目大意：
这是一个简化版本的问题，唯一的不同是在这个版本中 m = 1。给定两个整数数组 a_1, a_2, …, a_n 和 b_1, b_2, …, b_n。在执行任何操作之前，您可以按意愿重新排列每个数组的元素。然后，在一次操作中，如果您要执行以下两个动作，如果数组不为空：

从数组 a 中选择任意元素并将其删除（所有剩余元素将移至新数组 a），
从数组 b 中选择任意元素并将其删除（所有剩余元素将移至新数组 b）。
设 k 为两个数组的最终大小。您需要找到满足 a_i < b_i 对所有 1 ≤ i ≤ k 的最小操作数。

为了使问题更具挑战性，问题作者还给出了一个正整数 m。现在，您需要找到 m 对数组对 (c[i], b) 的答案之和，其中 1 ≤ i ≤ m。数组 c[i] 从 a 获得如下：

c[i]_1 = i，
c[i]_j = a_j，对于 2 ≤ j ≤ n。
输入输出数据格式：
每个测试包含多个测试用例。第一行包含一个整数 t (1 ≤ t ≤ 10^4) - 输入数据的集合数。接下来是它们的描述。

每个测试用例的第一行包含两个整数 n 和 m (2 ≤ n ≤ 10^5, m = 1) - 数组 a 和 b 的大小以及元素 a_1 的约束。

每个测试用例的第二行包含 n - 1 个整数 a_2, …, a_n (1 ≤ a_i ≤ 10^9)。

每个测试用例的第三行包含 n 个整数 b_1, b_2, …, b_n (1 ≤ b_i ≤ 10^9)。

保证所有测试用例的 n 之和不超过 10^5。

对于每个测试用例，输出所有数组对 (c_i, b) 的最小操作总数。题目大意： 这是一个简化版本的问题，唯一的不同是在这个版本中 m = 1。给定两个整数数组 a_1, a_2, …, a_n 和 b_1, b_2, …, b_n。在执行任何操作之前，您可以按意愿重新排列每个数组的元素。然后，在一次操作中，如果您要执行以下两个动作，如果数组不为空： 从数组 a 中选择任意元素并将其删除（所有剩余元素将移至新数组 a）， 从数组 b 中选择任意元素并将其删除（所有剩余元素将移至新数组 b）。 设 k 为两个数组的最终大小。您需要找到满足 a_i < b_i 对所有 1 ≤ i ≤ k 的最小操作数。 为了使问题更具挑战性，问题作者还给出了一个正整数 m。现在，您需要找到 m 对数组对 (c[i], b) 的答案之和，其中 1 ≤ i ≤ m。数组 c[i] 从 a 获得如下： c[i]_1 = i， c[i]_j = a_j，对于 2 ≤ j ≤ n。 输入输出数据格式： 每个测试包含多个测试用例。第一行包含一个整数 t (1 ≤ t ≤ 10^4) - 输入数据的集合数。接下来是它们的描述。 每个测试用例的第一行包含两个整数 n 和 m (2 ≤ n ≤ 10^5, m = 1) - 数组 a 和 b 的大小以及元素 a_1 的约束。 每个测试用例的第二行包含 n - 1 个整数 a_2, …, a_n (1 ≤ a_i ≤ 10^9)。 每个测试用例的第三行包含 n 个整数 b_1, b_2, …, b_n (1 ≤ b_i ≤ 10^9)。 保证所有测试用例的 n 之和不超过 10^5。 对于每个测试用例，输出所有数组对 (c_i, b) 的最小操作总数。