生活在二维平面的小 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^{\prime },y_0^{\prime },x_1^{\prime },y_1^{\prime },\dots ,x_{m-1}^{\prime },y_{m-1}^{\prime }$ 满足以下条件，或报告不存在这样的 $m$：

• $\sum _{i=0}^{m-1}(x_i^{\prime }+x_{imodn})=x$；
• $\sum _{i=0}^{m-1}(y_i^{\prime }+y_{imodn})=y$；
• $\mathrm{\forall }0\le i\le m-1,|x_i^{\prime }|+|y_i^{\prime }|\le k$。

特别地，$m=0$ 时，认为 $\sum _{i=0}^{m-1}(x_i^{\prime }+x_{imodn})$ 和 $\sum _{i=0}^{m-1}(y_i^{\prime }+y_{imodn})$ 均为 $0$。

输入格式

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

对于每组测试数据，

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

输出格式

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

样例 1

input

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

output

1
-1
0
399999999

explanation

该组样例共有四组测试数据。 - 对于第一组测试数据，取 $m=1$，$(x_0^{\prime },y_0^{\prime })=(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\le T\le 5\times {10}^4$；
• $1\le n\le {10}^5$，$1\le \sum n\le {10}^6$；
• $0\le |x|,|y|,|x_i|,|y_i|,k\le {10}^8$。

• 特殊性质 A：$\mathrm{\forall }0\le i\le n-1$，$|x_i|+|y_i|\le k$；
• 特殊性质 B：$k=0$；
• 特殊性质 C：$x_0=y_0=0$。

【提示】

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

时间限制：$\mathtt{\text{0.5s}}$

空间限制：$\mathtt{\text{512MB}}$