3958. [联合省选 2024] 季风

【题目背景】

生活在二维平面的小 X 准备拜访小 Y，但由于气候的变化，平面上刮起了季风。小 X 想知道季风的影响下，TA 至少要多少天能够到达小 Y 的家，但小 X 也是第一次遇见这种怪事，所以请精通算法的你来帮忙。

【题目描述】

给定 $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$。

【输入格式】

本题有多组测试数据。输入的第一行一个整数 $T$ 表示测试数据组数。

对于每组测试数据，

- 第一行四个整数 $n,k,x,y$；

- 接下来 $n$ 行，第 $i$ 行两个整数 $x_{i-1},y_{i-1}$。

【输出格式】

对于每组测试数据输出一行一个整数，如果存在满足题意的 $m$，输出其最小可能值，否则输出 $-1$。

【样例输入1】

4
1 2 2 2
1 1
1 2 -2 -2
1 1
1 2 0 0
1 1
2 100000000 100000000 100000000
-99999999 0
-100000000 0

【样例输出1】

1
-1
0
399999999

【样例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$。

- 特殊性质 A：$\forall 0\leq i \leq n-1$，$|x_i|+|y_i| \leq k$；

- 特殊性质 B：$k=0$；

- 特殊性质 C：$x_0=y_0=0$。

【提示】

本题输入文件较大，请使用较为快速的输入方式。

【附件】

wind.zip