P1009逐风（wind）

【题目背景】

一望无垠的大海上，现在刮起了妖风。

【题目描述】

Ehundategh 现在在大海上旅行，整个大海可以看作一个二维平面，Ehundategh 从 $(0,0)$ 出发，并且想到 $(x,y)$ 去，现在海上刮着妖风，但是经验丰富的 Ehundategh 判断出来，这是季风气候的标志，他发现，每一阵妖风都会在每一日的傍晚时分刮起，并且，妖风是有周期性的，以 $n$ 天为一个周期，也就是说，第 $n+1$ 天刮的风跟第 $1$ 天的风完全一样，进一步地讲，若有两天 $t_1,t_2$ 满足 $t_1\equiv t_2 \pmod n$，那么这两天的风是一模一样的。

Ehundategh 扬帆起航了，他在第 $1$ 天的白天启航，每一天白天，他都能先沿着 $x$ 轴方向走整数单位的距离，再沿着 $y$ 轴方向走整数单位的距离，也就是说，他只能上下左右行动，并且一次走一单位距离。由于船的码力有限，所以他每日行动的曼哈顿距离不能超过 $k$。每到傍晚，妖风便会刮起来，第 $i$ 天以及之后周期对应天数的妖风会让船沿 $x$ 轴正方向移动 $x_i$ 的距离，并沿 $y$ 轴正方向移动 $y_i$ 的距离（若距离为负，则视为向反方向移动）。

传闻，如果船只在某一天的妖风过去后，刚好被吹到自己的目的地，便会受到大海的保佑，于是，Ehundategh 想知道，至少要多少天才能够让自己恰好在那天傍晚被吹到 $(x,y)$，如果 $(x,y)=(0,0)$ 则输出 $0$，如果永远都做不到，则输出 $-1$。

【输入格式】

从文件 $\textbf{\textit{wind.in}}$ 中读入数据。

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

每组数据的第一行包含两个正整数 $n,k$ 和两个整数 $x,y$，表示妖风周期、船的码力以及目标地点的坐标。

接下来 $n$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 天的妖风会将船推动 $x_i,y_i$ 的距离。

【输出格式】

输出到文件 $\textbf{\textit{wind.out}}$ 中。

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

【样例 1 输入】

1421 2 2 231 141 2 -2 -251 161 2 0 071 182 100000000 100000000 1000000009-99999999 010-100000000 0

【样例 1 输出】

112-1304399999999

【说明/提示】

【样例 2】

见选手目录下的 $\textbf{\textit{wind/wind2.in}}$ 和 $\textbf{\textit{wind/wind2.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围，其中 $T=1000$，$\sum n=2\times 10^5$。

【样例 3】

见选手目录下的 $\textbf{\textit{wind/wind3.in}}$ 和 $\textbf{\textit{wind/wind3.ans}}$。

该组样例符合测试点 $13\sim 20$ 的数据范围，其中 $T=1000$，$\sum n=2\times 10^5$。

【样例 4】

见选手目录下的 $\textbf{\textit{wind/wind4.in}}$ 和 $\textbf{\textit{wind/wind4.ans}}$。

该组样例符合测试点 $13\sim 20$ 的数据范围，其中 $T=1500$，$\sum n=2\times 10^5$。

【数据范围】

特殊性质：对于所有 $1\leq i\leq n$，均满足 $\lvert x_i\rvert+\lvert y_i\rvert\leq k$。

对于 $100\%$ 的数据，保证：$1\leq T\leq 10^5$，$1\leq n\leq 10^5$，$1\leq k\leq 10^9$，$-10^9\leq x,y,x_i,y_i\leq 10^9$。