Migrated from Lutece 1569 Band Vect0r

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Control one's mind but lose heart.

The forth page recorded the skill to withdraw mind-control.

You just need to equivocate to your mind but honest to your heart.

The author of the poetry thought that the heart was composed by $N$ vectors in $M$ dimensions, and each vector has a weight $w_i$.

You need to choose some vectors which are linearly independent in $\mathbb{Z}_\mathrm{P}$ to compose a matrix, and the weight of the matrix equals the sum weight of the vectors you chosen.

Now you need to find a matrix with the maximum weight.

Let $a_{ij}$ denotes the $j_{th}$ component of the vector $A_i$, vectors $A_1, A_2, ..., A_s$ are linearly independent in $\mathbb{Z}_\mathrm{P}$ if and only if the equation $\sum_{i = 1}^s k_{i} \times a_{ij} \equiv 0 (\mathrm{mod}~P)$, $\forall~1 \leq j \leq M$, can only be satisfied by $k_i \equiv 0(\mathrm{mod}~P)$ for $i = 1, ..., s$.

Input

The first line contains three integers $N$, $M$ and $P$.

For the next $N$ lines, each line describes a vector.

In the $(i + 1)_{th}$ line, there are $M + 1$ integers $x_{i1}, x_{i2}, ..., x_{iM}, w_i$, where $x_{ij}$ is the $j_{th}$ component of the $i_{th}$ vector, and $w_i$ is the weight of the $i_{th}$ vector.

$1 \leq N, M \leq 200$, $0 \leq x_{ij} < P$, $0 \leq w_i \leq 10^9$, $2 \leq P \leq 10^9 + 9$ and $P$ is a prime.

Output

Print the maximum weight of the matrix.

Samples

3 2 2
0 1 1
1 0 2
1 1 3

5

Resources

The 15th UESTC Programming Contest Final