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

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

2 seconds
256 megabytes
Easy

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

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

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

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

Для кожного списку є число важливості r_i. Якщо відкрити всі перельоти зі списку , це принесе державі f(e) \cdot r_i грошових одиниць прибутку, де — кількість нових авіаперельотів, відкритих цього року, і

f(e) = (a \cdot e^2 + b \cdot e + c) \bmod n

(тут x \bmod y позначає залишок від ділення на ).

Козак Вус розмірковує, в якому порядку використовувати списки щороку, щоби максимізувати сукупний прибуток держави за років.

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

Input

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

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

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

Кожен із наступних рядків містить ціле число s_i (1 \le s_i \le n), а потім s_i різних цілих чисел t_{i1}, t_{i2}, \ldots, t_{is_i} (1 \le t_{ij} \le n) — список міст для -го року.

Гарантується, що всі числа у списку різні та сума всіх s_i не перевищує 3 \cdot 10^6.

Output

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

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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

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

Scoring

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

  2. ( балів) n \leq 10^3; m \leq 20; всі s_i = 2; c = 0;

  3. ( балів) n \leq 50; m \leq 7;

  4. ( балів) n \leq 50; m \leq 12;

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

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

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

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