Minimum Selection for Target Linear Function in Formal Power Series

We are given a prime (p) and (n) linear functions over (\mathbb{F}p) of the form (f_i(x)=a_i x+b_i) with (0\le a_i,b_i<p). Here, (x) is a formal power series variable. From these (n) functions, one may choose a set of (k) functions ({g_1(x),\dots,g_k(x)}) (possibly (k=0)). Define the set (H) as all values modulo (x^2) of products of arbitrary nonnegative powers of the (g_i(x)): [ H=\Big{,\prod{i=1}^k g_i(x)^{j_i}\bmod x^2 ;\Big|; j_i\in\mathbb{Z}_{\ge 0}\Big}] Note that by convention the polynomial (0\cdot x+1) (i.e. the constant (1)) is always in (H) even if (k=0).

For any given target polynomial of the form (Ax+B) with (A,B\in \mathbb{F}_p), your task is to find the minimum possible (k) (i.e. the size of the chosen subset) such that, by an appropriate choice of nonnegative exponents (j_i), you can make

[ \prod_{i=1}^k g_i(x)^{j_i} \equiv Ax+B \pmod{x^2}. ] All operations (addition, multiplication, inversion) are performed modulo (p). If no choice of (k) functions (and exponents) can yield (Ax+B\in H), output (-1).

A hint on the computation: For any linear function (g(x)=a x+b) (with (b\neq0)), one may verify that for any (j\ge 0)

[ g(x)^j \equiv b^j + j,a,b^{j-1} x \pmod{x^2}. ] Thus if you choose a set (S) of functions and exponents ({j_i}_{i\in S}), the product equals

[ \left(\prod_{i\in S}b_i^{j_i}\right)\Bigl(1+\sum_{i\in S}\frac{j_i a_i}{b_i}x\Bigr) \pmod{x^2}. ] This leads to two conditions:

1. (\prod_{i\in S} b_i^{j_i} \equiv B) modulo (p).
2. (\prod_{i\in S} b_i^{j_i} \cdot \Big(\sum_{i\in S}\frac{j_i a_i}{b_i}\Big) \equiv A) modulo (p).

When (B\neq 0), note that functions with (b_i=0) can only be used with exponent 0 (since (0^j=0) for (j\ge 1) and would force the constant term to zero). In the case (B=0), you must pick at least one function with (b_i=0) and assign it a positive exponent (and take care with the linear term, since if more than one such function is used with a positive exponent the product becomes 0). In fact, when (B=0):

• If (A=0) then choosing a single (f_i) with (b_i=0) and exponent (j\ge2) (or even (j=1) if (a_i=0)) gives (0), so the answer is (1).
• If (A\neq 0) then you need to choose exactly one function (f_i(x)=a_i x+0) with (a_i\equiv A) and set its exponent to (1) (while all others are taken with exponent 0). Otherwise, the answer is (-1).

When (B\neq0), by writing each function (f_i(x)=a_i x+b_i) with (b_i\neq 0) in its powered form and taking discrete logarithms on the constant part (with respect to a primitive root modulo (p)) the problem becomes equivalent to a subgroup membership (or subset‐sum) problem in two independent modular settings. Since the exponents (j_i) can be chosen arbitrarily large (and then adjusted modulo the order of (b_i)), a necessary and sufficient condition for a chosen subset (S) to be viable is that the pair ((\ell, r)=(\log_g(B), A\cdot B^{-1})) is in the subgroup generated by ({(\log_g(b_i), a_i,b_i^{-1}) : i\in S}) (with the first coordinate modulo (p-1) and the second modulo (p)).

Your program is to output the minimum (k) (possibly (0)) for which some subset of (k) functions can yield (Ax+B). If no such subset exists, output (-1).

inputFormat

The first line contains four integers (p), (n), (A), and (B) (with (p) prime and (0\le A,B< p)). Each of the following (n) lines contains two integers (a_i) and (b_i) ((0\le a_i,b_i<p)), representing the linear function (f_i(x)=a_i x+b_i).

outputFormat

Output a single integer: the minimum (k) for which there exists a selection of (k) functions (and appropriate nonnegative exponents for each) such that (Ax+B) belongs to (H). If no such selection exists, output (-1).

sample

7 3 2 1
1 2
3 1
4 3

2