E. Омкар и последний этаж
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Омкар строит дом. Он хочет решить, как составить план пола на последнем этаже.

Пол Омкара изначально выглядит как $$$n$$$ строк по $$$m$$$ нолей. ($$$1 \le n,m \le 100$$$). Каждая строка разделена на отрезки, причем каждый $$$0$$$ в строке находится ровно в $$$1$$$ отрезке. Для каждого отрезка для каждой строки Омкар может заменить ровно один из $$$0$$$, содержащихся в этом отрезке, на $$$1$$$. Омкар определяет качество пола как сумму квадратов сумм значений в каждом столбце, т.е. если сумма значений в $$$i$$$-м столбце равна $$$q_i$$$, то качество пола равно $$$\sum_{i = 1}^m q_i^2$$$.

Помогите Омкару найти максимальное качество, которое может иметь пол.

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

Первая строка содержит два целых числа, $$$n$$$ и $$$m$$$ ($$$1 \le n,m \le 100$$$), которые являются количеством строк и количеством столбцов соответственно.

Затем вы получите описание отрезков в каждой строке. Для каждой строки $$$i$$$ от $$$1$$$ до $$$n$$$: Первая строка содержит одно целое число $$$k_i$$$ ($$$1 \le k_i \le m$$$)  — которое является количеством отрезков в строке $$$i$$$. $$$j$$$-я из следующих $$$k_i$$$ строк содержит два целых числа $$$l_{i,j}$$$ и $$$r_{i,j}$$$, которые являются левой и правой границей (обе включительно), соответственно, $$$j$$$-го отрезка $$$i$$$-й строки. Гарантируется, что $$$l_{i,1} = 1$$$, $$$l_{i,j} \leq r_{i,j}$$$ для всех $$$1 \le j \le k_i$$$, $$$r_{i,j-1} + 1 = l_{i,j}$$$ для всех $$$2 \le j \le k_i$$$, и $$$r_{i,k_i} = m$$$.

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

Выведите одно целое число, которое является максимально возможным качеством пола.

Пример
Входные данные
4 5
2
1 2
3 5
2
1 3
4 5
3
1 1
2 4
5 5
3
1 1
2 2
3 5
Выходные данные
36
Примечание

Данный пример соответствует следующей диаграмме. Ячейки в одном ряду с одинаковым номером являются частью одного и того же отрезка.

Наиболее оптимальным планом является:

Сумма $$$1$$$-го столбца равна $$$4$$$, сумма $$$2$$$-го столбца равна $$$2$$$, сумма $$$3$$$-го и $$$4$$$-го столбцов равна $$$0$$$, а сумма $$$5$$$-го столбца равна $$$4$$$.

Качество этого плана этажа составляет $$$4^2 + 2^2 + 0^2 + 0^2 + 4^2 = 36$$$. Можно показать, что нет плана пола с более высоким качеством.