Description

Farmer John owns $3N$ cows (with $1 \le N \le 500{,}000$), numbered $0 \ldots 3N - 1$. Each cow $i$ has an integer weight $W_i$ and a utility rating $U_i$.

He may enter a group of $N$ cows into the Grand Farm-off. He wants to choose $N$ cows whose total utility is maximized. If multiple sets of $N$ cows achieve the same maximum total utility, he prefers the set with the minimum possible total weight.

Among all selections of $N$ cows that maximize the total utility, find the minimum possible total weight, and output the remainder when this total weight is divided by $M$ (with $10{,}000{,}000 \le M \le 1{,}000{,}000{,}000$).

To speed up input, the weights and utilities are generated by polynomials. For each cow $0 \le i < 3N$,

Note that these formulae can generate duplicate values; your algorithm should handle this properly. Also, $0 \le W_i < d$ and $0 \le U_i < h$.

Input Format

Line 1: Ten space-separated integers $N$, $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$, $M$.

Output Format

Line 1: A single integer — the remainder when the minimum possible total weight (among all selections of $N$ cows that maximize total utility) is divided by $M$.

2 0 1 5 55555555 0 1 0 55555555 55555555 

51 

Hint

The functions generate weights of 5, 6, 9, 14, 21, and 30 along with utilities of 0, 1, 8, 27, 64, and 125.

The two cows with the highest utility are cows 5 and 6, and their combined weight is $21 + 30 = 51$.

Translated by ChatGPT 5