Background

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.

Problem Description

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$.

Input Format

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}$.

Output Format

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$.

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

Hint

[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$.

• 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