P9826 [ICPC 2020 Shanghai R] Rice Arrangement

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

有多个测试用例。输入的第一行包含一个整数 $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$。

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

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