G. Битва против дракона
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Отряд из $$$n$$$ воинов защищает замок от нападения дракона. Между драконом и замком есть $$$m$$$ баррикад.

Воины пронумерованы от $$$1$$$ до $$$n$$$. $$$i$$$-й воин знает $$$k_i$$$ атак: $$$j$$$-я из них наносит $$$a_{i,j}$$$ урона дракону и может быть применена только есть между замком и драконом ровно $$$b_{i,j}$$$ баррикад.

Воины ходят один за другим, начиная с воина $$$1$$$. После того как воин $$$n$$$ завершит свой ход, считается суммарный урон, нанесенный дракону. $$$i$$$-й воин в свой ход совершает одно из трех возможных действий:

  1. разрушить одну баррикаду (если еще остались);
  2. применить одну из $$$k_i$$$ своих атак;
  3. пропустить ход.

Суммарный урон считается, как сумма уронов от атак, примененных воинами, которые в свой ход выбрали атаковать. Какой наибольший суммарный урон воины могут нанести дракону?

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) — количество воинов и начальной количество баррикад.

Затем следуют описания атак каждого воина. $$$i$$$-е описание состоит из трех строк.

В первой строке записано одно целое число $$$k_i$$$ ($$$1 \le k_i \le m + 1$$$) — количество атак, которые знает $$$i$$$-й воин.

Во второй строке записаны $$$k_i$$$ целых чисел $$$a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — урон от каждой атаки.

В третьей строке записаны $$$k_i$$$ целых чисел $$$b_{i,1}, b_{i,2}, \dots, b_{i,k_i}$$$ ($$$0 \le b_{i,j} \le m$$$) — необходимое число баррикад для каждой атаки. $$$b_{i,j}$$$ для $$$i$$$-го воина попарно различные. Атаки приведены в порядке возрастания необходимого числа баррикад, то есть $$$b_{i,1} < b_{i,2} < \dots < b_{i,k_i}$$$.

Сумма $$$k_i$$$ по всем воинам не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Выведите одно целое число — наибольший суммарный урон, который воины могут нанести дракону.

Примеры
Входные данные
2 4
1
2
4
2
10 5
3 4
Выходные данные
10
Входные данные
3 3
1
1
0
1
20
2
1
100
3
Выходные данные
100
Входные данные
2 1
2
10 10
0 1
2
30 20
0 1
Выходные данные
30
Примечание

В первом примере лучший выбор следующий:

  • воин $$$1$$$ уничтожает баррикаду, остается $$$3$$$ баррикады;
  • воин $$$2$$$ применяет свою первую атаку (он может это сделать, потому что $$$b_{1,1}=3$$$, что равно текущему числу баррикад).

Суммарный урон равен $$$10$$$.

Если бы первый воин применил свою атаку или пропустил свой ход, то второй мог бы применить только вторую атаку. Таким образом, урон был бы $$$2+5=7$$$ или $$$5$$$.

Во втором примере первый воин пропускает свой ход, второй воин пропускает свой ход, а третий воин применяет свою единственную атаку.

В третьем примере есть два варианта:

  • оба воина применяют свои вторые атаки;
  • первый воин уничтожает одну баррикаду, а второй воин применяет свою первую атаку.

В обоих случаях получается $$$30$$$ суммарного урона.