Minimal m for Feasible Adjustment Sequence

Given four integers \(n, k, x, y\) and \(2n\) integers \(x_0, y_0, x_1, y_1, \dots, x_{n-1}, y_{n-1}\), find the smallest 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:

• \(\displaystyle \sum_{i=0}^{m-1} (x'_i + x_{i \bmod n}) = x\).
• \(\displaystyle \sum_{i=0}^{m-1} (y'_i + y_{i \bmod n}) = y\).
• For every \(0 \le i \le m-1\), \(|x'_i|+|y'_i| \le k\).

By convention, when \(m=0\), both sums are taken to be \(0\). If no such \(m\) exists, output \(-1\).

Hint: For a fixed \(m\), if we denote \(q = \lfloor m/n \rfloor\) and \(r = m \bmod n\), then define \[ S_x(m) = q \cdot \Bigl(\sum_{j=0}^{n-1} x_j\Bigr) + \sum_{j=0}^{r-1} x_j, \quad S_y(m) = q \cdot \Bigl(\sum_{j=0}^{n-1} y_j\Bigr) + \sum_{j=0}^{r-1} y_j. \] The condition to be met is: \[ |x - S_x(m)| + |y - S_y(m)| \le m \cdot k. \]

inputFormat

The input consists of two lines:

• The first line contains four space-separated integers: \(n, k, x, y\).
• The second line contains \(2n\) space-separated integers: \(x_0, y_0, x_1, y_1, \dots, x_{n-1}, y_{n-1}\).

outputFormat

Output a single integer: the smallest non-negative integer \(m\) that satisfies the conditions, or \(-1\) if no such \(m\) exists.

sample

1 5 10 0
10 0

1