Description

Wowo 是一位好客的新疆大叔。$k$ 位客人将在 Wowo 家中围着一张大圆桌享用维吾尔抓饭（一种传统的维吾尔食物）。圆桌周围均匀地放置了 $n$ 把椅子（$n \ge k$）。每位客人坐在一把椅子上，并且没有两位客人坐在同一把椅子上。桌子上有 $k$ 碗维吾尔抓饭。每碗抓饭都放在某把椅子旁边（无论是否有客人坐在上面）。没有两碗抓饭放在同一位置。

作为服务员，你需要为每个人分配一碗维吾尔抓饭。桌子可以旋转，因此每次你可以顺时针或逆时针旋转 $\frac{2\pi}{n}$ 度。碗会随着桌子一起旋转，而椅子和客人不动。当一碗维吾尔抓饭在某位客人面前时，他可以选择拿起它或等待另一碗。

你希望尽量减少桌子旋转的总次数，以便每个人都能尽快用餐。

（正式定义：桌子的边界是一个圆。$n$ 把椅子位于圆上的 $n$ 个点，其凸包是一个有 $n$ 个顶点的正多边形。我们按逆时针顺序将这些点命名为 $0,\ldots, n-1$。第 $i$ 碗抓饭最初位于点 $b_i$ ($0\le b_i<n$)。第 $i$ 位客人最初位于点 $a_i$ ($0\le a_i < n$)。如果你逆时针旋转桌子，位于点 $b_i$ ($1\le i\le k$) 的碗将在旋转后移动到点 $(b_i+ 1) \bmod n$。如果你顺时针旋转桌子，位于点 $b_i$ ($1\le i\le k$) 的碗将在旋转后移动到点 $(b_i-1) \bmod n$。($x\bmod n$ 定义为最小的非负整数 $r$ 使得 $x-r$ 是 $n$ 的倍数。)）

Input Format

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n,k$ ($1\le n \le 10^9,1 \le k \le \min(n,1000)$)，表示桌子的大小以及人数和维吾尔抓饭的碗数。

第二行有 $k$ 个整数 $a_1,a_2,\dots,a_k$ ($0 \le a_i < n$)，表示客人的位置。没有两位客人共享同一位置。

第三行有 $k$ 个整数 $b_1,b_2,\dots,b_k$ ($0 \le b_i < n$)，表示碗的初始位置。没有两碗维吾尔抓饭放在同一位置。

保证所有测试用例中 $k$ 的总和不超过 $5000$。

Output Format

对于每个测试用例，输出使得每位客人能恰好得到一碗维吾尔抓饭的最小旋转总次数。

1
4 2
0 3
1 2

2

1
14 5
0 12 13 8 9
9 2 6 13 5

6

Hint

题面翻译由 ChatGPT-4o 提供。