{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eWowo is a hospitable Xinjiang uncle. $$$k$$$ guests will have Uyghur Polo (a traditional Uyghur food) in Wowo\u0027s 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 (\u003cspan class\u003d\"tex-font-style-bf\"\u003ewith or without\u003c/span\u003e some guest sitting on it). No two bowls locate at the same position.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/9d9b1bd65cdeeac17f2f12e6d3d1e999?v\u003d1726278102\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eAs 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.\u003c/p\u003e\u003cp\u003eYou want to minimize the total times of table rotating so that everybody can have meals as quickly as possible.\u003c/p\u003e\u003cp\u003e(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\u0026lt;n$$$) initially. The $$$i$$$-th guest is at point $$$a_i$$$ ($$$0\\le a_i \u0026lt; 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$$$.))\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $$$T$$$, indicating the number of test cases. For each test case:\u003c/p\u003e\u003cp\u003eThe 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. \u003c/p\u003e\u003cp\u003eIn the second line, there are $$$k$$$ integers $$$a_1,a_2,\\dots,a_k$$$ ($$$0 \\le a_i \u0026lt; n$$$), indicating the positions of the persons. No two guests share the same position.\u003c/p\u003e\u003cp\u003eIn the third line, there are $$$k$$$ integers $$$b_1,b_2,\\dots,b_k$$$ ($$$0 \\le b_i \u0026lt; n$$$), indicating the initial positions of the bowls. No two bowls of Uyghur Polo locate at the same position.\u003c/p\u003e\u003cp\u003eIt is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$5000$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output the minimal total times of rotations such that each guest can have exactly one bowl of Uyghur Polo.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n4 2\n0 3\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n14 5\n0 12 13 8 9\n9 2 6 13 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}