B. Соберём портфель вместе
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мебибайт
ввод
стандартный ввод
вывод
стандартный вывод

В компании [REDACTED] думают запустить несколько проектов.

Каждый проект может быть запущен разными способами, но только одним из них, или не запущен вообще.

Команда аналитиков предоставила ожидаемые затраты и выручку для каждого способа запуска.

Система устроена так, что затраты тратятся из фиксированного бюджета, который руководство утвердило заранее. При этом любая полученная выручка не увеличивает бюджет для старта ещё не запущенных проектов.

Руководство интересуется только максимальной суммарной выручкой. То есть их не интересуют суммарные затраты, кроме того, что они вписываются в рамки заданного бюджета.

Вас, как высококвалифицированного специалиста, просят найти максимальную суммарную выручку.

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

Первая строка содержит два целых числа $$$n$$$ и $$$b$$$ — количество проектов и выделенный бюджет ($$$1 \le n \le 20$$$, $$$0 \le b \le 10^9$$$).

Далее записаны $$$n$$$ проектов, каждый с новой строки. Описание $$$i$$$-го проекта начинается со строки, содержащей целое число $$$k_i$$$ — количество возможных запусков ($$$1 \le k_i \le 20$$$). Далее в $$$k_i$$$ строках записаны два целых числа $$$r_{ij}$$$ и $$$e_{ij}$$$ — выручка и затраты соответственно в случае запуска $$$i$$$-го проекта $$$j$$$-м способом ($$$0 \le r_{ij}, e_{ij} \le 10^9$$$).

Суммарное количество всех способов запуска для всех проектов не превосходит $$$20$$$ ($$$\sum k_i \le 20$$$).

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

Выведите одно целое число $$$r$$$ — максимальную суммарную выручку.

Примеры
Входные данные
2 10
2
100 10
80 9
1
10 1
Выходные данные
100
Входные данные
2 5
2
200 3
100 2
2
10 2
20 3
Выходные данные
210