{"problem":{"name":"[省选联考 2024] 季风","description":{"content":"给定 $n,k,x,y$ 和 $2n$ 个整数 $x_0,y_0,x_1,y_1,\\dots,x_{n-1},y_{n-1}$。 找到最小的**非负整数** $m$，使得存在 $2m$ 个实数 $x_0',y_0',x_1',y_1',\\dots,x_{m-1}',y_{m-1}'$ 满足以下条件，或报告不存在这样的 $m$： - $\\sum \\limits_{i=0}^{m-1} (x_i'+","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10217"},"statements":[{"statement_type":"Markdown","content":"给定 $n,k,x,y$ 和 $2n$ 个整数 $x_0,y_0,x_1,y_1,\\dots,x_{n-1},y_{n-1}$。\n\n找到最小的**非负整数** $m$，使得存在 $2m$ 个实数 $x_0',y_0',x_1',y_1',\\dots,x_{m-1}',y_{m-1}'$ 满足以下条件，或报告不存在这样的 $m$：\n- $\\sum \\limits_{i=0}^{m-1} (x_i'+x_{i \\bmod n})=x$；\n- $\\sum \\limits_{i=0}^{m-1} (y_i'+y_{i \\bmod n})=y$；\n- $\\forall 0\\leq i\\leq m-1,|x_i'|+|y_i'|\\leq k$。\n\n特别地，$m=0$ 时，认为 $\\sum \\limits_{i=0}^{m-1} (x_i'+x_{i \\bmod n})$ 和 $\\sum \\limits_{i=0}^{m-1} (y_i'+y_{i \\bmod n})$ 均为 $0$。\n\n## Input\n\n**本题有多组测试数据**。输入的第一行一个整数 $T$ 表示测试数据组数。\n\n对于每组测试数据，\n- 第一行四个整数 $n,k,x,y$；\n- 接下来 $n$ 行，第 $i$ 行两个整数 $x_{i-1},y_{i-1}$。\n\n## Output\n\n对于每组测试数据输出一行一个整数，如果存在满足题意的 $m$，输出其最小可能值，否则输出 $-1$。\n\n[samples]\n\n## Background\n\n生活在二维平面的小 X 准备拜访小 Y，但由于气候的变化，平面上刮起了季风。小 X 想知道季风的影响下，TA 至少要多少天能够到达小 Y 的家，但小 X 也是第一次遇见这种怪事，所以请精通算法的你来帮忙。\n\n## Note\n\n**【样例 1 解释】**\n\n该组样例共有四组测试数据。\n- 对于第一组测试数据，取 $m=1$，$(x_0',y_0')=(1,1)$ 满足条件，可以证明不存在更小的 $m$ 满足条件；\n- 对于第二组测试数据，可以证明不存在任何非负整数 $m$ 满足条件；\n- 对于第三组测试数据，取 $m=0$ 满足条件，可以证明不存在更小的 $m$ 满足条件。\n\n**【样例 2】**\n\n见附件中的 `wind2.in/ans`。\n\n该组样例共有八十组测试数据，所有测试数据均满足 $n=1$，其中测试数据 $1\\sim 20$ 满足特殊性质 A，$21\\sim 40$ 满足特殊性质 B，$41\\sim 60$ 满足特殊性质 C。\n\n**【样例 3】**\n\n见附件中的 `wind3.in/ans`。\n\n该组样例共有六十组测试数据，所有测试数据均满足 $n=200$，其中测试数据 $1\\sim 20$ 满足特殊性质 A，$21\\sim 40$ 满足特殊性质 B。\n\n**【子任务】**\n\n设 $\\sum n$ 为单个测试点内所有测试数据 $n$ 的和。对于所有测试数据：\n\n- $1\\leq T\\leq 5\\times 10^4$；\n- $1\\leq n\\leq 10^5$，$1\\leq \\sum n \\leq 10^6$；\n- $0\\leq |x|,|y|,|x_i|,|y_i|,k\\leq 10^8$。\n\n| 测试点编号 | $n\\leq$ | $\\sum n\\leq$ | 特殊性质 |\n| :----------: | :----------: | :----------: | :----------: |\n| $1$ | $1$ | $300$ | A |\n| $2$ | $1$ | $300$ | B |\n| $3$ | $1$ | $300$ | C |\n| $4$ | $1$ | $300$ | 无 |\n| $5$ | $200$ | $5000$ | A |\n| $6$ | $200$ | $5000$ | B |\n| $7$ | $200$ | $5000$ | 无 |\n| $8$ | $10^4$ | $10^5$ | A |\n| $9$ | $10^4$ | $10^5$ | B |\n| $10$ | $10^5$ | $10^6$ | 无 |\n\n- 特殊性质 A：$\\forall 0\\leq i \\leq n-1$，$|x_i|+|y_i| \\leq k$；\n- 特殊性质 B：$k=0$；\n- 特殊性质 C：$x_0=y_0=0$。\n\n**【提示】**\n\n本题输入文件较大，请使用较为快速的输入方式。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10217","tags":["各省省选","2024","O2优化"],"sample_group":[["4\n1 2 2 2\n1 1\n1 2 -2 -2\n1 1\n1 2 0 0\n1 1\n2 100000000 100000000 100000000\n-99999999 0\n-100000000 0","1\n-1\n0\n399999999"]],"created_at":"2026-03-03 11:09:25"}}