#SXLK2024A. 季风

季风

题目背景

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

题目描述

给定 n,k,x,yn,k,x,y2n2n 个整数 x0,y0,x1,y1,,xn1,yn1x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}

找到最小的非负整数 mm,使得存在 2m2m 个实数 x0,y0,x1,y1,,xm1,ym1x_0',y_0',x_1',y_1',\dots,x_{m-1}',y_{m-1}' 满足以下条件,或报告不存在这样的 mm

  • i=0m1(xi+ximodn)=x\sum \limits_{i=0}^{m-1} (x_i'+x_{i \bmod n})=x
  • i=0m1(yi+yimodn)=y\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n})=y
  • 0im1,xi+yik\forall 0\leq i\leq m-1,|x_i'|+|y_i'|\leq k

特别地,m=0m=0 时,认为 i=0m1(xi+ximodn)\sum \limits_{i=0}^{m-1} (x_i'+x_{i \bmod n})i=0m1(yi+yimodn)\sum \limits_{i=0}^{m-1} (y_i'+y_{i \bmod n}) 均为 00

输入格式

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

对于每组测试数据,

  • 第一行四个整数 n,k,x,yn,k,x,y
  • 接下来 nn 行,第 ii 行两个整数 xi1,yi1x_{i-1},y_{i-1}

输出格式

对于每组测试数据输出一行一个整数,如果存在满足题意的 mm,输出其最小可能值,否则输出 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
0
399999999

【样例 1 解释】

该组样例共有四组测试数据。

  • 对于第一组测试数据,取 m=1m=1(x0,y0)=(1,1)(x_0',y_0')=(1,1) 满足条件,可以证明不存在更小的 mm 满足条件;
  • 对于第二组测试数据,可以证明不存在任何非负整数 mm 满足条件;
  • 对于第三组测试数据,取 m=0m=0 满足条件,可以证明不存在更小的 mm 满足条件。

【样例 2】

见附件中的 wind2.in/ans

该组样例共有八十组测试数据,所有测试数据均满足 n=1n=1,其中测试数据 1201\sim 20 满足特殊性质 A,214021\sim 40 满足特殊性质 B,416041\sim 60 满足特殊性质 C。

【样例 3】

见附件中的 wind3.in/ans

该组样例共有六十组测试数据,所有测试数据均满足 n=200n=200,其中测试数据 1201\sim 20 满足特殊性质 A,214021\sim 40 满足特殊性质 B。

【子任务】

n\sum n 为单个测试点内所有测试数据 nn 的和。对于所有测试数据:

  • 1T5×1041\leq T\leq 5\times 10^4
  • 1n1051\leq n\leq 10^51n1061\leq \sum n \leq 10^6
  • 0x,y,xi,yi,k1080\leq |x|,|y|,|x_i|,|y_i|,k\leq 10^8
测试点编号 nn\leq n\sum n\leq 特殊性质
11 11 300300 A
22 B
33 C
44
55 200200 50005000 A
66 B
77
88 10410^4 10510^5 A
99 B
1010 10510^5 10610^6
  • 特殊性质 A:0in1\forall 0\leq i \leq n-1xi+yik|x_i|+|y_i| \leq k
  • 特殊性质 B:k=0k=0
  • 特殊性质 C:x0=y0=0x_0=y_0=0

【提示】

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