Omkar is building a house. He wants to decide how to make the floor plan for the last floor.

Omkar's floor starts out as $n$ rows of $m$ zeros ($1 \le n,m \le 100$). Every row is divided into intervals such that every $0$ in the row is in exactly $1$ interval. For every interval for every row, Omkar can change exactly one of the $0$s contained in that interval to a $1$. Omkar defines the quality of a floor as the sum of the squares of the sums of the values in each column, i. e. if the sum of the values in the $i$-th column is $q_i$, then the quality of the floor is $\sum_{i = 1}^m q_i^2$.

Help Omkar find the maximum quality that the floor can have.


-----Input-----

The first line contains two integers, $n$ and $m$ ($1 \le n,m \le 100$), which are the number of rows and number of columns, respectively.

You will then receive a description of the intervals in each row. For every row $i$ from $1$ to $n$: The first row contains a single integer $k_i$ ($1 \le k_i \le m$), which is the number of intervals on row $i$. The $j$-th of the next $k_i$ lines contains two integers $l_{i,j}$ and $r_{i,j}$, which are the left and right bound (both inclusive), respectively, of the $j$-th interval of the $i$-th row. It is guaranteed that all intervals other than the first interval will be directly after the interval before it. Formally, $l_{i,1} = 1$, $l_{i,j} \leq r_{i,j}$ for all $1 \le j \le k_i$, $r_{i,j-1} + 1 = l_{i,j}$ for all $2 \le j \le k_i$, and $r_{i,k_i} = m$.


-----Output-----

Output one integer, which is the maximum possible quality of an eligible floor plan.


-----Example-----
Input
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

Output
36



-----Note-----

The given test case corresponds to the following diagram. Cells in the same row and have the same number are a part of the same interval.

 [Image] 

The most optimal assignment is:

 [Image] 

The sum of the $1$st column is $4$, the sum of the $2$nd column is $2$, the sum of the $3$rd and $4$th columns are $0$, and the sum of the $5$th column is $4$.

The quality of this floor plan is $4^2 + 2^2 + 0^2 + 0^2 + 4^2 = 36$. You can show that there is no floor plan with a higher quality.

Difficulty: interview

Starter code:

Solutions:
from sys import stdin, stdout


def __starting_point():

    def omkar_and_last_floor(a, n, m):

        dp = [[0 for c in range(m)] for r in range(m)]

        #print(dp)
        for r in range(m):
            for l in range(r,-1,-1):
                for k in range(l, r+1):
                    cnt = 0
                    for i in range(n):
                        if l <= a[i][k][0] and a[i][k][1] <= r:
                            cnt += 1
                    lr = cnt*cnt
                    if k-1 >= l:
                        lr += dp[l][k-1]
                    if k+1 <= r:
                        lr += dp[k + 1][r]

                    dp[l][r] = max(dp[l][r], lr)
        #print(dp)
        return dp[0][m-1]


    n, m = list(map(int, stdin.readline().split()))
    a = [[[0,0] for c in range(m)] for r in range(n)]
    for i in range(n):
        k = int(stdin.readline())
        for j in range(k):
            l, r = list(map(int, stdin.readline().split()))
            for x in range(l, r+1):
                a[i][x-1][0] = l-1
                a[i][x-1][1] = r-1

    print(omkar_and_last_floor(a, n, m))


__starting_point()

import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')


from functools import lru_cache


def solve(n, m, a):

    b = [[] for _ in range(m)]
    for j in range(m):
        for l, r, i in a:
            if l <= j <= r:
                b[j].append((l, r, i))

    @lru_cache(maxsize=None)
    def go(left, right):
        if left > right:
            return 0

        best = 0
        for mid in range(left, right + 1):
            cnt = 0
            for l, r, i in b[mid]:
                if l <= mid <= r and l >= left and r <= right:
                    cnt += 1

            best = max(best, cnt * cnt + go(left, mid - 1) + go(mid + 1, right))

        return best

    return go(0, m-1)


def main():
    n, m = ria()
    a = set()
    for i in range(n):
        k = ri()
        for j in range(k):
            l, r = ria()
            l -= 1
            r -= 1
            a.add((l, r, i))

    wi(solve(n, m, a))


def __starting_point():
    main()

__starting_point()

from sys import stdin, stdout
 
 
def __starting_point():
 
    def omkar_and_last_floor(a, n, m):
 
        dp = [[0 for c in range(m)] for r in range(m)]
 
        #print(dp)
        for r in range(m):
            for l in range(r,-1,-1):
                for k in range(l, r+1):
                    cnt = 0
                    for i in range(n):
                        if l <= a[i][k][0] and a[i][k][1] <= r:
                            cnt += 1
                    lr = cnt*cnt
                    if k-1 >= l:
                        lr += dp[l][k-1]
                    if k+1 <= r:
                        lr += dp[k + 1][r]
 
                    dp[l][r] = max(dp[l][r], lr)
        #print(dp)
        return dp[0][m-1]
 
 
    n, m = map(int, stdin.readline().split())
    a = [[[0,0] for c in range(m)] for r in range(n)]
    for i in range(n):
        k = int(stdin.readline())
        for j in range(k):
            l, r = map(int, stdin.readline().split())
            for x in range(l, r+1):
                a[i][x-1][0] = l-1
                a[i][x-1][1] = r-1
 
    print(omkar_and_last_floor(a, n, m))
__starting_point()

from bisect import *
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    dp = [[0] * (w + 1) for _ in range(w + 1)]
    for d in range(1, w + 1):
        for l in range(w - d + 1):
            r = l + d
            cnt = [0] * (w + 1)
            for i in range(h):
                sl=bisect_left(seg[i], l)
                sr=bisect_right(seg[i], r)
                if sl==sr:continue
                b = seg[i][sl]
                e = seg[i][sr - 1]
                cnt[b] += 1
                cnt[e] -= 1
            #for j in range(l, r): cnt[j + 1] += cnt[j]
            #print(cnt)
            #mx = max(cnt)
            #if mx == 0: continue
            for j in range(l, r):
                cnt[j + 1] += cnt[j]
                if cnt[j] == 0: continue
                dp[l][r] = max(dp[l][r], cnt[j] ** 2 + dp[l][j] + dp[j + 1][r])
    print(dp[0][w])
    #p2D(dp)

h,w=MI()
seg=[[0] for _ in range(h)]
for i in range(h):
    for _ in range(II()):
        l,r=MI()
        seg[i].append(r)
solve()


from bisect import *
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    dp = [[0] * (w + 1) for _ in range(w + 1)]
    for d in range(1, w + 1):
        for l in range(w - d + 1):
            r = l + d
            cnt = [0] * (w + 1)
            for i in range(h):
                sl=bisect_left(seg[i], l)
                sr=bisect_right(seg[i], r)
                if sl==sr:continue
                b = seg[i][sl]
                e = seg[i][sr - 1]
                cnt[b] += 1
                cnt[e] -= 1
            #for j in range(l, r): cnt[j + 1] += cnt[j]
            #print(cnt)
            #mx = max(cnt)
            #if mx == 0: continue
            for j in range(l, r):
                cnt[j + 1] += cnt[j]
                if cnt[j] == 0: continue
                dp[l][r] = max(dp[l][r], cnt[j] ** 2 + dp[l][j] + dp[j + 1][r])
    print(dp[0][w])
    #p2D(dp)

h,w=MI()
seg=[[0] for _ in range(h)]
for i in range(h):
    for _ in range(II()):
        l,r=MI()
        seg[i].append(r)
solve()


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def solve():
	n, m = mints()
	lines = []
	rows = [[0]*(m+2) for i in range(n)]
	col = [n]*(m+2)
	lstart = [[] for i in range(m+2)]
	lend = [[] for i in range(m+2)]
	dp = [[0]*(m+2) for i in range(m+2)]
	for i in range(n):
		for j in range(mint()):
			l, r = mints()
			lstart[l].append((i, r + 1))
			lend[r + 1].append((i, l))
	for i in range(1,m+2):
		for r, start in lend[i]:
			#print("end", r, start, i-1)
			for p in range(start, i):
				rows[r][p] -= 1
				if rows[r][p] == 0:
					col[p] += 1
		for r, end in lstart[i]:
			#print("start", r, i, end)
			for p in range(i, end):
				rows[r][p] += 1
				if rows[r][p] == 1:
					col[p] -= 1
		bcol = col.copy()
		brows = [rows[i].copy() for i in range(n)]
		#print(i, col)
		cc = [None]*(i-1)
		for j in range(i-1):
			for r, start in lend[j]:
				for p in range(start, j):
					rows[r][p] -= 1
					if rows[r][p] == 0:
						col[p] += 1
			for r, end in lstart[j]:
				for p in range(j, end):
					rows[r][p] += 1
					if rows[r][p] == 1:
						col[p] -= 1
			cc[j] = col.copy()

		for j in range(i-2,-1,-1):
			d = 0
			col = cc[j]
			for p in range(j+1, i):
				d = max(d, dp[j][p] + dp[p][i] + col[p]**2)
			dp[j][i] = d
			#print(j, i, col, d)
		col = bcol
		rows = brows
	print(dp[0][m+1])

solve()