AT_abc416_d [ABC416D] Match, Mod, Minimize 2

题目描述

给你长度为 $N$ 的序列 $a=a_1,a_2,\cdots,a_n$ 和 $b=b_1,b_2,\cdots,b_n$,以及一个正整数 $m$。 你可以自由地重新排列 $a$ 中的元素,求 $\displaystyle \sum_{i=1}^n \left((a_i+b_i) \bmod m\right)$ 的最小可能值。 $T$ 组数据,分别求解。

输入格式

从标准输入读入数据。 第一行,一个正整数 $T$,表示有 $T$ 组数据。 接下来 $3T$ 行,每 $3$ 行描述一组数据。 对于每组数据: 第一行,两个正整数 $n, m$。 第二行,$n$ 个非负整数 $a_i$。 第三行,$n$ 个非负整数 $b_i$。

输出格式

输出共 $T$ 行。 对于每组数据输出一个非负整数表示答案。

说明/提示

**【样例 1 解释】** 对于第一个测试用例,将 $a$ 重新排列为 $\{4, 3, 1\}$ 后原式 $= 5$,可以证明其为最小值。 **【数据范围】** - $1\le T \le 10^5$; - $1\le n\le 3\times 10^5$; - $1\le m\le 10^9$; - $0\le a_i,b_i < m$; - $n$ 的总和不超过 $3\times 10^5$; - 所有输入值均为非负整数。