A93079.「联合省选 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$。

从文件 wind.in 中读入数据。

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

对于每组测试数据，

• 第一行四个整数 $n,k,x,y$；
• 接下来 $n$ 行，第 $i$ 行两个整数 $x_{i-1},y_{i-1}$。

输出到文件 wind.out 中。

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