Авіашляхи Потоколяндії

Нещодавно Козака Вуса було обрано на посаду голови Міністерства інфраструктури Потоколяндії, у якій $n$ міст, пронумерованих цілими числами від $1$ до $n$.

Зараз у Потоколяндії всі люди використовують автомобілі і немає жодного авіаперельоту. Саме тому Міністерство вирішило відкрити перші авіаперельоти в Потоколяндії. Відповідно до законодавства країни між кожною парою міст може бути не більше одного авіаперельоту.

Відомо, що у Козака є план відкриття авіаперельотів на наступні $m$ років. У нього є $m$ списків міст. Кожного року він хоче вибрати один список зі ще не вибраних та відкрити авіасполучення між кожною парою міст у цьому списку, що ще не є сполученими авіаперельотом. Зверніть увагу, що якщо в списку є два міста, між якими вже є авіапереліт, то відкривати новий забороняється.

Крім того, усім жителям Потоколяндії відомі так звані три найважливіші числа: $a$, $b$ та $c$.

Для кожного списку $i$ є певне число $r_i$ — його важливість. Відомо, що якщо відкрити всі авіасполучення між містами в $i$-му списку, то це принесе $f(e)\cdot r_i$ грошових одиниць прибутку державі, де $e$ — кількість нових авіаперельотів, які були відкриті цього року, а $f(e)$ — деяка функція, що визначається так: $f(e)=(a\cdot e^2+b\cdot e+c)\mathrm{mod}n$ (де $x\mathrm{mod}y$ — залишок від ділення $x$ на $y$).

Козак Вус задумався, який саме список потрібно використовувати кожного року, щоб сумарно через $m$ років принести якомога більший прибуток державі.

Допоможіть Козаку, знайшовши максимальну кількість грошових одиниць, яку він може принести державі, якщо він може кожного року вибирати список, який він не використовував раніше, та відкрити нові авіаперельоти між кожною парою міст у цьому списку, що ще не сполучені авіашляхом.

Giriş verilənləri

Перший рядок містить три цілі числа $n$, $m$, $g$ ($1\le n\le 10^6$, $1\le m\le 20$, $0\le g\le 8$) — кількість міст, списків у Потоколяндії та номер блоку, до якого належить тест, відповідно.

Другий рядок містить три цілі числа $a$, $b$, $c$ ($0\le a,b,c<n$) — три найважливіші числа Потоколяндії.

Третій рядок містить $m$ цілих чисел $r_1,r_2,\dots ,r_m$ ($0\le r_i\le 10^6$) — важливість $i$-го списку.

Кожний із наступних $m$ рядків містить ціле число $s_i$ ($1\le s_i\le n$) та $s_i$ цілих чисел $t_{i1},t_{i2},\dots ,t_{i{s}_i}$ ($1\le t_{ij}\le n)$ — кількість міст в $i$-му списку та міста в цьому списку. Гарантується, що всі числа в списку різні.

Гарантується, що сума значень $s$ не перевищує $3\cdot 10^6$.

Çıxış verilənləri

Виведіть одне ціле число — максимальну кількість грошових одиниць, яку може принести Козак державі.

Nümunələr

Qeyd

У першому прикладі можна використовувати списки в такому порядку: $[1,2,3]$.

У другому прикладі можна використовувати списки в такому порядку: $[2,1,3,4]$.

Qiymətləndirmə

1. ($5$ балів) $n\le 10^3$; $m\le 20$; усі значення $s_i$ рівні $2$; не існує двох списків, яким належить одна і та сама пара міст;

2. ($7$ балів) $n\le 10^3$; $m\le 20$; усі значення $s_i$ рівні $2$; $c=0$;

3. ($16$ балів) $n\le 50$; $m\le 7$;

4. ($14$ балів) $n\le 50$; $m\le 12$;

5. ($8$ балів) $n\le 10^5$; $m\le 3$;

6. ($17$ балів) $n\le 5\cdot 10^4$; $m\le 10$;

7. ($7$ балів) $n\le 2\cdot 10^5$; $m\le 16$;

8. ($26$ балів) без додаткових обмежень.