P10217 [NOI Qualifier Joint Contest 2024] Monsoon.

Little X, who lives on a 2D plane, is going to visit Little Y. However, due to climate changes, a monsoon is blowing on the plane. Little X wants to know, under the influence of the monsoon, at least how many days it will take to reach Little Y’s home. Since Little X is also seeing this strange situation for the first time, please ask you, who are skilled in algorithms, to help.

Given $n, k, x, y$ and $2n$ integers $x_0, y_0, x_1, y_1, \dots, x_{n-1}, y_{n-1}$. Find the minimum **non-negative integer** $m$ such that there exist $2m$ real numbers $x_0', y_0', x_1', y_1', \dots, x_{m-1}', y_{m-1}'$ satisfying the following conditions, or report that no such $m$ exists: - $\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$. In particular, when $m = 0$, both $\sum \limits_{i=0}^{m-1} (x_i' + x_{i \bmod n})$ and $\sum \limits_{i=0}^{m-1} (y_i' + y_{i \bmod n})$ are considered to be $0$.

**This problem has multiple test cases**. The first line contains an integer $T$ denoting the number of test cases. For each test case, - The first line contains four integers $n, k, x, y$; - The next $n$ lines contain two integers each; the $i$-th line contains $x_{i-1}, y_{i-1}$.

For each test case, output one integer per line. If there exists an $m$ satisfying the statement, output the minimum possible value; otherwise output $-1$.

**[Sample 1 Explanation]** This sample contains four test cases. - For the first test case, take $m = 1$, $(x_0', y_0') = (1, 1)$, which satisfies the conditions. It can be proven that no smaller $m$ can satisfy the conditions; - For the second test case, it can be proven that there is no non-negative integer $m$ that satisfies the conditions; - For the third test case, take $m = 0$, which satisfies the conditions. It can be proven that no smaller $m$ can satisfy the conditions. **[Sample 2]** See the attached `wind2.in/ans`. This sample contains eighty test cases. All testdata satisfy $n = 1$, where testdata $1 \sim 20$ satisfy Special Property A, $21 \sim 40$ satisfy Special Property B, and $41 \sim 60$ satisfy Special Property C. **[Sample 3]** See the attached `wind3.in/ans`. This sample contains sixty test cases. All testdata satisfy $n = 200$, where testdata $1 \sim 20$ satisfy Special Property A, and $21 \sim 40$ satisfy Special Property B. **[Subtasks]** Let $\sum n$ be the sum of $n$ over all test cases within a single test point. For all testdata: - $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$. | Test Point ID | $n \leq$ | $\sum n \leq$ | Special Property | | :----------: | :----------: | :----------: | :----------: | | $1$ | $1$ | $300$ | A | | $2$ | $1$ | $300$ | B | | $3$ | $1$ | $300$ | C | | $4$ | $1$ | $300$ | None | | $5$ | $200$ | $5000$ | A | | $6$ | $200$ | $5000$ | B | | $7$ | $200$ | $5000$ | None | | $8$ | $10^4$ | $10^5$ | A | | $9$ | $10^4$ | $10^5$ | B | | $10$ | $10^5$ | $10^6$ | None | - Special Property A: $\forall 0 \leq i \leq n-1$, $|x_i| + |y_i| \leq k$; - Special Property B: $k = 0$; - Special Property C: $x_0 = y_0 = 0$. **[Hint]** The input file for this problem is large. Please use a faster input method. Translated by ChatGPT 5