CF1949B Charming Meals

捷克菜肴有 $n$ 道开胃菜和 $n$ 道主菜。第 $i$ 道开胃菜的辣度为 $a_i$，第 $i$ 道主菜的辣度为 $b_i$。 一顿典型的捷克餐由恰好一道开胃菜和一道主菜组成。你需要将 $n$ 道开胃菜和 $n$ 道主菜两两配对，组成 $n$ 份餐食，每道开胃菜和每道主菜都只能被使用一次。 你希望让每份餐食的两道菜的辣度尽可能不同。每份餐食的“魅力值”定义为开胃菜和主菜辣度的绝对值之差。也就是说，若一份餐食由辣度为 $x$ 的开胃菜和辣度为 $y$ 的主菜组成，则其魅力值为 $|x-y|$。 你希望最大化所有 $n$ 份餐食中最小的魅力值。请问你能获得的最大最小魅力值是多少？

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1\le t\le 1000$），表示测试用例的数量。接下来是 $t$ 组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$1\le n\le 5000$），表示开胃菜和主菜的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0\le a_i\le 10^9$），表示 $n$ 道开胃菜的辣度。 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$0\le b_i\le 10^9$），表示 $n$ 道主菜的辣度。 保证所有测试用例中 $n^2$ 的总和不超过 $25\times 10^6$。

对于每组测试用例，输出一个整数，表示你能获得的最大最小魅力值。

在第一个测试用例中，无论如何配对开胃菜和主菜，每份餐食都会有一道辣度为 $0$ 的开胃菜和一道辣度为 $1000000000$ 的主菜，因此每份餐食的魅力值都是 $1000000000$。 在第二个测试用例中，一种最优的配对方式为：$(1, 5)$，$(2, 4)$，$(3, 1)$，$(4, 2)$，$(5, 3)$。对应的餐食魅力值分别为 $4$、$2$、$2$、$2$、$2$。此时最小魅力值为 $2$。 在第三个测试用例中，一种最大化最小魅力值的方式是将三道辣度为 $0$ 的开胃菜与三道辣度为 $100$ 的主菜配对，将三道辣度为 $100$ 的开胃菜与三道辣度为 $0$ 的主菜配对。这样每份餐食的魅力值恰好为 $100$。 由 ChatGPT 4.1 翻译