CF2170C Quotient and Remainder

You are given two integer arrays: $ q_1, q_2, \dots, q_n $ and $ r_1, r_2, \dots, r_n $ , as well as an integer $ k $ . You can perform the following operation any number of times (possibly zero): 1. Choose two integers $ x $ and $ y $ such that - $ 1 \le y < x \le k $ ; - there exists an index $ i $ such that $ q_i = \left\lfloor \frac{x}{y} \right\rfloor $ (rounded down); - there exists an index $ j $ such that $ r_j = x \bmod y $ . 2. Remove $ q_i $ from the array $ q $ and $ r_j $ from the array $ r $ . If there are multiple occurrences of $ q_i $ in the array $ q $ , only one occurrence is removed; same for $ r_j $ and the array $ r $ . Calculate the maximum number of operations that you can perform on the given arrays $ q $ and $ r $ .

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 2 \le k \le 10^{18} $ ) — the size of the arrays $ q $ and $ r $ and the upper limit for $ x $ and $ y $ . The second line of each test case contains $ n $ integers $ q_1, q_2, \dots, q_n $ ( $ 1 \le q_i \le 10^9 $ ) — the array $ q $ . The third line contains $ n $ integers $ r_1, r_2, \dots, r_n $ ( $ 1 \le r_i \le 10^9 $ ) — the array $ r $ . Additional constraints on the input: the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, print one integer — the maximum number of operations that you can perform on the given arrays.

In the first test case, one operation can be performed: you can choose $ x = 69 $ and $ y = 42 $ . Then $ \left\lfloor \frac{69}{42} \right\rfloor = 1 = q_1 $ and $ 69 \bmod 42 = 27 = r_1 $ . In the second test case, it is impossible to perform any operations, as suitable $ x $ and $ y $ cannot be found. In the third test case, three operations can be performed: 1. $ x = 42 $ , $ y = 17 $ : $ \left\lfloor \frac{42}{17} \right\rfloor = 2 = q_3 $ and $ 42 \bmod 17 = 8 = r_2 $ ; 2. $ x = 41 $ , $ y = 16 $ : $ \left\lfloor \frac{41}{16} \right\rfloor = 2 = q_4 $ and $ 41 \bmod 16 = 9 = r_1 $ ; 3. $ x = 20 $ , $ y = 12 $ : $ \left\lfloor \frac{20}{12} \right\rfloor = 1 = q_5 $ and $ 20 \bmod 12 = 8 = r_4 $ ; After these operations, you'll get arrays $ q = [5, 4] $ and $ r = [9, 100] $ , and there are no more operations you can perform.