Maximum Non-Divisible Sum from LCG Sequences

Little Roman is exploring linear congruential generators (LCGs), one of the oldest and best known pseudorandom number generator algorithms. An LCG starts with a non-negative integer seed \(x_0\) (where \(0 \le x_0 < c\)) and produces an infinite sequence \(x_i\) (with \(0 \le x_i < c\)) defined by the recurrence relation:

\(x_{i+1} = (a\,x_i + b) \mod c\)

Here, \(a\), \(b\), and \(c\) are non-negative integers.

Roman has n different LCGs. The \(j\)-th LCG is defined by parameters \(x^{(j)}_0\), \(a^{(j)}\), \(b^{(j)}\), and \(c^{(j)}\) and produces the sequence \(x^{(j)}_i\). He wants to choose one number from each sequence such that the total sum

[ S = \sum_{j=1}^{n} x^{(j)}_{t_j} ]

is as large as possible, subject to the constraint that (S \mod k \neq 0) for a given positive integer (k). In other words, if the maximum sum (obtained by taking the maximum number from each LCG) is divisible by (k), then Roman may choose a slightly smaller number from one of the LCGs to break this divisibility. If it is impossible to achieve a sum that is not divisible by (k), output (-1).

Hint: Each LCG is periodic (the period is at most \(c\)). You can simulate each sequence until a cycle is detected to find the maximum value and the largest value less than the maximum available in that cycle. Then, if \(S\) (the sum of all maximum values) is divisible by \(k\), try reducing one component by the minimal amount that makes \(S \mod k \neq 0\).

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \le n \le 10^3\), \(1 \le k \le 10^9\)). Each of the following \(n\) lines contains four integers: \(x_0\), \(a\), \(b\), and \(c\) (with \(0 \le x_0 < c\) and \(0 \le a,b \le 10^9\), \(1 \le c \le 10^9\)) describing one LCG.

outputFormat

Output a single integer: the maximum possible sum \(S\) satisfying \(S \mod k \neq 0\). If no such sum exists, output \(-1\).

sample

1 2
0 1 1 2

1