{"problem":{"name":"[ICPC 2020 Shanghai R] Rice Arrangement","description":{"content":"Wowo is a hospitable Xinjiang uncle. $k$ guests will have Uyghur Polo (a traditional Uyghur food) in Wowo's house around a big round table. $n$ ($n\\ge k$) chairs are placed around the table uniformly.","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9826"},"statements":[{"statement_type":"Markdown","content":"Wowo is a hospitable Xinjiang uncle. $k$ guests will have Uyghur Polo (a traditional Uyghur food) in Wowo's house around a big round table. $n$ ($n\\ge k$) chairs are placed around the table uniformly. Each guest sits on a chair and no two guests sit on the same chair. $k$ bowls of Uyghur Polo are on the table. Each bowl is next to some chair ($\\textbf{with or without}$ some guest sitting on it). No two bowls locate at the same position.\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/q3gqhsvq.png)\n\nAs a waiter, you are supposed to assign each person with exactly one bowl of Uyghur Polo. The table can be rotated, so each time you can turn it $\\frac{2\\pi}{n}$ degrees clockwise or counterclockwise. The bowls turn with the table while the chairs and guests do not move. When one bowl of Uyghur Polo is in front of a guest, he can either take it or wait for another.\n\nYou want to minimize the total times of table rotating so that everybody can have meals as quickly as possible.\n\n(Formal definition: The boundary of the table is a circle. $n$ chairs are at $n$ points on the circle whose convex hull is a regular polygon with $n$ vertices. We name the points $0,\\ldots, n-1$ in counterclockwise order. The $i$-th bowl is at point $b_i$ ($0\\le b_i<n$) initially. The $i$-th guest is at point $a_i$ ($0\\le a_i < n$) initially. If you turn the table counterclockwise, the bowl at point $b_i$ ($1\\le i\\le k$) will be moved to point $(b_i+ 1) \\bmod n$ after the rotation. If you turn the table clockwise, the bowl at point $b_i$ ($1\\le i\\le k$) will be moved to point $(b_i-1) \\bmod n$ after the rotation. ($x\\bmod n$ is defined as the smallest nonnegative integer $r$ such that $x-r$ is a multiple of $n$.))\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n,k$ ($1\\le n \\le 10^9,1 \\le k \\le \\min(n,1000)$) indicating the size of the table and the number of persons and bowls of Uyghur Polo. \n\nIn the second line, there are $k$ integers $a_1,a_2,\\dots,a_k$ ($0 \\le a_i < n$), indicating the positions of the persons. No two guests share the same position.\n\nIn the third line, there are $k$ integers $b_1,b_2,\\dots,b_k$ ($0 \\le b_i < n$), indicating the initial positions of the bowls. No two bowls of Uyghur Polo locate at the same position.\n\nIt is guaranteed that the sum of $k$ over all test cases does not exceed $5000$.\n\n## Output\n\nFor each test case, output the minimal total times of rotations such that each guest can have exactly one bowl of Uyghur Polo.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9826","tags":["数学","贪心","2020","上海","O2优化","ICPC"],"sample_group":[["1\n4 2\n0 3\n1 2","2"],["1\n14 5\n0 12 13 8 9\n9 2 6 13 5","6"]],"created_at":"2026-03-03 11:09:25"}}