[省选联考 2024] 季风

给定 $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'+x_{i \bmod n})=x$； - $\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n})=y$； - $\forall 0\leq i\leq m-1,|x_i'|+|y_i'|\leq k$。 特别地，$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$。 ## Input **本题有多组测试数据**。输入的第一行一个整数 $T$ 表示测试数据组数。 对于每组测试数据， - 第一行四个整数 $n,k,x,y$； - 接下来 $n$ 行，第 $i$ 行两个整数 $x_{i-1},y_{i-1}$。 ## Output 对于每组测试数据输出一行一个整数，如果存在满足题意的 $m$，输出其最小可能值，否则输出 $-1$。 [samples] ## Background 生活在二维平面的小 X 准备拜访小 Y，但由于气候的变化，平面上刮起了季风。小 X 想知道季风的影响下，TA 至少要多少天能够到达小 Y 的家，但小 X 也是第一次遇见这种怪事，所以请精通算法的你来帮忙。 ## Note **【样例 1 解释】** 该组样例共有四组测试数据。 - 对于第一组测试数据，取 $m=1$，$(x_0',y_0')=(1,1)$ 满足条件，可以证明不存在更小的 $m$ 满足条件； - 对于第二组测试数据，可以证明不存在任何非负整数 $m$ 满足条件； - 对于第三组测试数据，取 $m=0$ 满足条件，可以证明不存在更小的 $m$ 满足条件。 **【样例 2】** 见附件中的 `wind2.in/ans`。 该组样例共有八十组测试数据，所有测试数据均满足 $n=1$，其中测试数据 $1\sim 20$ 满足特殊性质 A，$21\sim 40$ 满足特殊性质 B，$41\sim 60$ 满足特殊性质 C。 **【样例 3】** 见附件中的 `wind3.in/ans`。 该组样例共有六十组测试数据，所有测试数据均满足 $n=200$，其中测试数据 $1\sim 20$ 满足特殊性质 A，$21\sim 40$ 满足特殊性质 B。 **【子任务】** 设 $\sum n$ 为单个测试点内所有测试数据 $n$ 的和。对于所有测试数据： - $1\leq T\leq 5\times 10^4$； - $1\leq n\leq 10^5$，$1\leq \sum n \leq 10^6$； - $0\leq |x|,|y|,|x_i|,|y_i|,k\leq 10^8$。 | 测试点编号 | $n\leq$ | $\sum n\leq$ | 特殊性质 | | :----------: | :----------: | :----------: | :----------: | | $1$ | $1$ | $300$ | A | | $2$ | $1$ | $300$ | B | | $3$ | $1$ | $300$ | C | | $4$ | $1$ | $300$ | 无 | | $5$ | $200$ | $5000$ | A | | $6$ | $200$ | $5000$ | B | | $7$ | $200$ | $5000$ | 无 | | $8$ | $10^4$ | $10^5$ | A | | $9$ | $10^4$ | $10^5$ | B | | $10$ | $10^5$ | $10^6$ | 无 | - 特殊性质 A：$\forall 0\leq i \leq n-1$，$|x_i|+|y_i| \leq k$； - 特殊性质 B：$k=0$； - 特殊性质 C：$x_0=y_0=0$。 **【提示】** 本题输入文件较大，请使用较为快速的输入方式。