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.

Source: codeforces | Difficulty: VERY_HARD
Tags: Dynamic programming

Amortized analysis

Greedy algorithms


Solutions:
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]
				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])
(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()


def solve():
	(n, m) = map(int, input().split())
	(le, ri) = ([[0] * m for i in range(n)], [[0] * m for i in range(n)])
	for i in range(n):
		t = int(input())
		for _ in range(t):
			(x, y) = map(int, input().split())
			x -= 1
			y -= 1
			for j in range(x, y + 1):
				le[i][j] = x
				ri[i][j] = y
	dp = [[0] * m for i in range(m)]
	for i in range(m):
		c = 0
		for j in range(n):
			if le[j][i] == ri[j][i] == i:
				c += 1
		dp[i][i] = c * c
	for l in range(m - 2, -1, -1):
		for r in range(l + 1, m):
			c = 0
			for i in range(n):
				if le[i][l] >= l and ri[i][l] <= r:
					c += 1
			dp[l][r] = c * c + dp[l + 1][r]
			c = 0
			for i in range(n):
				if le[i][r] >= l and ri[i][r] <= r:
					c += 1
			dp[l][r] = max(dp[l][r], c * c + dp[l][r - 1])
			for j in range(l + 1, r):
				c = 0
				for i in range(n):
					if le[i][j] >= l and ri[i][j] <= r:
						c += 1
				dp[l][r] = max(dp[l][r], c * c + dp[l][j - 1] + dp[j + 1][r])
	return dp[0][-1]
import sys
input = lambda : sys.stdin.readline().rstrip()
print(solve())


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)]
		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)
		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()


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()


import sys

def Myfun():
	(n, m) = map(int, fun2().split())
	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(fun3()):
			(l, r) = fun1()
			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]:
			for p in range(start, i):
				rows[r][p] -= 1
				if rows[r][p] == 0:
					col[p] += 1
		for (r, end) in lstart[i]:
			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)]
		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
		col = bcol
		rows = brows
	print(dp[0][m + 1])

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

def fun3():
	return int(fun2())

def fun1():
	return map(int, fun2().split())
Myfun()


import sys

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

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

def mints():
	return 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]:
			for p in range(start, i):
				rows[r][p] -= 1
				if rows[r][p] == 0:
					col[p] += 1
		for (r, end) in lstart[i]:
			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)]
		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
		col = bcol
		rows = brows
	print(dp[0][m + 1])
solve()


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
s = [[[0 for _ in range(m)] for _ in range(m)] for _ in range(m)]
for i in range(n):
	k = int(input())
	for j in range(k):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		for x in range(l, r + 1):
			s[l][r][x] += 1
for i in range(m):
	for j in range(max(1, i), m):
		for k in range(i, j + 1):
			s[i][j][k] += s[i][j - 1][k]
for i in range(m - 2, -1, -1):
	for j in range(i, m):
		for k in range(i, j + 1):
			s[i][j][k] += s[i + 1][j][k]
f = [[0 for _ in range(m)] for _ in range(m)]
for i in range(m - 1, -1, -1):
	for j in range(i, m):
		for k in range(i, j + 1):
			a = f[i][k - 1] if i <= k - 1 else 0
			b = f[k + 1][j] if k + 1 <= j else 0
			f[i][j] = max(f[i][j], a + b + s[i][j][k] ** 2)
print(f[0][m - 1])


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [(ch, len(list(g))) for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

@lru_cache(None)
def dp(l, r):
	if r < l:
		return 0
	res = 0
	for k in range(l, r + 1):
		c = 0
		for i in range(n):
			(a, b) = bnd[i][k]
			if l <= a and b <= r:
				c += 1
		res = max(res, c * c + dp(l, k - 1) + dp(k + 1, r))
	return res
t = 1
for i in range(t):
	(n, m) = RL()
	bnd = [[[] for j in range(m + 1)] for i in range(n)]
	for i in range(n):
		k = N()
		for a in range(k):
			(l, r) = RL()
			for j in range(l, r + 1):
				bnd[i][j] = [l, r]
	ans = dp(1, m)
	print(ans)