The Grand Farm-off

Farmer John owns $3N$ cows ($1 \le N \le 500{,}000$), numbered $0$ through $3N-1$. Cow $i$ has an integer weight $W_i$ and an integer utility $U_i$, both produced by the formulas below.

He is entering the Grand Farm-off, a farming competition where he shows off his cows to the wider agricultural community. He may enter exactly $N$ cows, and he wants his selection to have the maximum possible sum of utility.

Several different groups of $N$ cows may attain the same maximum utility sum. Because the competition might impose a limit on the total weight of the entered cows, Farmer John prefers, as a secondary priority, the group whose total weight is as small as possible.

Among all groups of $N$ cows that maximize the total utility, find the one with the smallest total weight, and print that minimum total weight modulo $M$ ($10{,}000{,}000 \le M \le 1{,}000{,}000{,}000$).

Each cow $i$ ($0 \le i < 3N$) is generated as follows:

$$W_i = (a \cdot i^5 + b \cdot i^2 + c) \bmod d$$

$$U_i = (e \cdot i^5 + f \cdot i^3 + g) \bmod h$$

The coefficients satisfy:

• $0 \le a, b, c, e, f, g \le 1{,}000{,}000{,}000$
• $10{,}000{,}000 \le d, h \le 1{,}000{,}000{,}000$

The formulas sometimes produce duplicate values, so your algorithm must handle duplicates correctly.

• One line with ten space-separated integers: $N$, $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$, and $M$.

• A single integer: the minimum total weight over all selections of $N$ cows that maximize the total utility, taken modulo $M$.

The formulas generate weights $5, 6, 9, 14, 21, 30$ and utilities $0, 1, 8, 27, 64, 125$. The two cows with the highest utility are cow $i=4$ and cow $i=5$, whose combined weight is $21 + 30 = 51$.