Recently Ivan noticed an array a while debugging his code. Now Ivan can't remember this array, but the bug he was trying to fix didn't go away, so Ivan thinks that the data from this array might help him to reproduce the bug.

Ivan clearly remembers that there were n elements in the array, and each element was not less than 1 and not greater than n. Also he remembers q facts about the array. There are two types of facts that Ivan remembers:  1 l_{i} r_{i} v_{i} — for each x such that l_{i} ≤ x ≤ r_{i} a_{x} ≥ v_{i};  2 l_{i} r_{i} v_{i} — for each x such that l_{i} ≤ x ≤ r_{i} a_{x} ≤ v_{i}. 

Also Ivan thinks that this array was a permutation, but he is not so sure about it. He wants to restore some array that corresponds to the q facts that he remembers and is very similar to permutation. Formally, Ivan has denoted the cost of array as follows:

$\operatorname{cos} t = \sum_{i = 1}^{n}(\operatorname{cnt}(i))^{2}$, where cnt(i) is the number of occurences of i in the array.

Help Ivan to determine minimum possible cost of the array that corresponds to the facts!


-----Input-----

The first line contains two integer numbers n and q (1 ≤ n ≤ 50, 0 ≤ q ≤ 100).

Then q lines follow, each representing a fact about the array. i-th line contains the numbers t_{i}, l_{i}, r_{i} and v_{i} for i-th fact (1 ≤ t_{i} ≤ 2, 1 ≤ l_{i} ≤ r_{i} ≤ n, 1 ≤ v_{i} ≤ n, t_{i} denotes the type of the fact).


-----Output-----

If the facts are controversial and there is no array that corresponds to them, print -1. Otherwise, print minimum possible cost of the array.


-----Examples-----
Input
3 0

Output
3

Input
3 1
1 1 3 2

Output
5

Input
3 2
1 1 3 2
2 1 3 2

Output
9

Input
3 2
1 1 3 2
2 1 3 1

Output
-1

Source: codeforces | Difficulty: HARD
Tags: Flows and cuts


Solutions:
import sys

def is_feasible(cnt, L, R):
	n = len(R)
	inter = [(L[i], R[i]) for i in range(n)]
	right = []
	feasible = True
	for x in range(n):
		for p in inter:
			if p[0] == x:
				right.append(p[1])
		while right and min(right) < x:
			right.remove(min(right))
		for quantity in range(cnt[x]):
			if right:
				right.remove(min(right))
			else:
				feasible = False
	return feasible
(n, q) = list(map(int, sys.stdin.readline().split()))
L = [0 for i in range(n)]
R = [n - 1 for i in range(n)]
for restriction in range(q):
	(t, l, r, v) = list(map(int, sys.stdin.readline().split()))
	if t == 1:
		for k in range(l - 1, r):
			L[k] = max(L[k], v - 1)
	else:
		for k in range(l - 1, r):
			R[k] = min(R[k], v - 1)
is_possible = all(map(lambda x, y: x <= y, L, R))
if not is_possible:
	print(-1)
else:
	cnt = {x: L.count(x) for x in range(n)}
	had_pair = True
	while had_pair:
		had_pair = False
		for x in range(n):
			for y in range(n):
				if cnt[x] > cnt[y] + 1:
					cnt[x] -= 1
					cnt[y] += 1
					has_pair = True
					if not is_feasible(cnt, L, R):
						cnt[x] += 1
						cnt[y] -= 1
						has_pair = False
					had_pair = had_pair or has_pair
	ans = sum([cnt[x] * cnt[x] for x in range(n)])
	print(ans)


import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp

class MinCostFlowwithDijkstra:
	INF = 1 << 60

	def __init__(self, N):
		self.N = N
		self.Edge = [[] for _ in range(N)]

	def add_edge(self, st, en, cap, cost):
		self.Edge[st].append([en, cap, cost, len(self.Edge[en])])
		self.Edge[en].append([st, 0, -cost, len(self.Edge[st]) - 1])

	def get_mf(self, so, si, fl):
		N = self.N
		INF = self.INF
		res = 0
		Pot = [0] * N
		geta = N
		prv = [None] * N
		prenum = [None] * N
		while fl:
			dist = [INF] * N
			dist[so] = 0
			Q = [so]
			while Q:
				(cost, vn) = divmod(hpp(Q), geta)
				if dist[vn] < cost:
					continue
				for enum in range(len(self.Edge[vn])):
					(vf, cap, cost, _) = self.Edge[vn][enum]
					cc = dist[vn] + cost - Pot[vn] + Pot[vf]
					if cap > 0 and dist[vf] > cc:
						dist[vf] = cc
						prv[vf] = vn
						prenum[vf] = enum
						hp(Q, cc * geta + vf)
			if dist[si] == INF:
				return -1
			for i in range(N):
				Pot[i] -= dist[i]
			cfl = fl
			vf = si
			while vf != so:
				cfl = min(cfl, self.Edge[prv[vf]][prenum[vf]][1])
				vf = prv[vf]
			fl -= cfl
			res -= cfl * Pot[si]
			vf = si
			while vf != so:
				e = self.Edge[prv[vf]][prenum[vf]]
				e[1] -= cfl
				self.Edge[vf][e[3]][1] += cfl
				vf = prv[vf]
		return res
(N, Q) = list(map(int, readline().split()))
T = MinCostFlowwithDijkstra(2 * N + 2)
geta = N
candi = [set(range(N)) for _ in range(N)]
for _ in range(Q):
	(t, l, r, v) = list(map(int, readline().split()))
	l -= 1
	r -= 1
	v -= 1
	if t == 1:
		for vn in range(l, r + 1):
			for i in range(v - 1, -1, -1):
				if i in candi[vn]:
					candi[vn].remove(i)
	else:
		for vn in range(l, r + 1):
			for i in range(v + 1, N):
				if i in candi[vn]:
					candi[vn].remove(i)
if not all(candi):
	print(-1)
else:
	source = 2 * N
	sink = 2 * N + 1
	for i in range(N):
		T.add_edge(source, i, 1, 0)
		for v in candi[i]:
			T.add_edge(i, geta + v, 1, 0)
		for j in range(N):
			T.add_edge(i + geta, sink, 1, 2 * j + 1)
	print(T.get_mf(source, sink, N))


from collections import deque
from heapq import heappop, heappush

class Edge(object):
	__slots__ = ('x', 'y', 'cap', 'cost', 'inv')

	def __repr__(self):
		return f'{self.x}-->{self.y} ({self.cap} , {self.cost})'

class MCFP:

	def __init__(self):
		self.G = []

	def add(self, x, y, cap, cost):
		G = self.G
		G.extend(([] for i in range(max(0, max(x, y) + 1 - len(G)))))
		e = Edge()
		e.x = x
		e.y = y
		e.cap = cap
		e.cost = cost
		z = Edge()
		z.x = y
		z.y = x
		z.cap = 0
		z.cost = -cost
		e.inv = z
		z.inv = e
		G[x].append(e)
		G[y].append(z)

	def solve(self, src, tgt, inf=float('inf')):
		(n, G) = (len(self.G), self.G)
		flowVal = flowCost = 0
		phi = [0] * n
		prev = [None] * n
		inQ = [0] * n
		cntQ = 1
		dist = [inf] * n
		while 1:
			self.shortest(src, phi, prev, inQ, dist, inf, cntQ)
			if prev[tgt] == None:
				break
			z = inf
			x = tgt
			while x != src:
				e = prev[x]
				z = min(z, e.cap)
				x = e.x
			x = tgt
			while x != src:
				e = prev[x]
				e.cap -= z
				e.inv.cap += z
				x = e.x
			flowVal += z
			flowCost += z * (dist[tgt] - phi[src] + phi[tgt])
			for i in range(n):
				if prev[i] != None:
					phi[i] += dist[i]
					dist[i] = inf
			cntQ += 1
			prev[tgt] = None
		return (flowVal, flowCost)

	def shortest(self, src, phi, prev, inQ, dist, inf, cntQ):
		(n, G) = (len(self.G), self.G)
		Q = [(dist[src], src)]
		inQ[src] = cntQ
		dist[src] = 0
		while Q:
			(_, x) = heappop(Q)
			inQ[x] = 0
			dx = dist[x] + phi[x]
			for e in G[x]:
				y = e.y
				dy = dx + e.cost - phi[y]
				if e.cap > 0 and dy < dist[y]:
					dist[y] = dy
					prev[y] = e
					if inQ[y] != cntQ:
						inQ[y] = cntQ
						heappush(Q, (dy, y))
		return (dist, prev)

	def __repr__(self):
		(n, G) = (len(self.G), self.G)
		s = []
		for i in range(n):
			s.append('    G[{}]:'.format(i))
			s.append('\n'.join(('        {}'.format(e) for e in G[i])))
		return '\n'.join(s)
import sys
ints = (int(x) for x in sys.stdin.read().split())
sys.setrecursionlimit(3000)

def main():
	(n, q) = (next(ints) for i in range(2))
	leq = [n - 1] * n
	geq = [0] * n
	for q in range(q):
		(t, l, r, v) = (next(ints) for i in range(4))
		for i in range(l - 1, r):
			if t == 1:
				geq[i] = max(geq[i], v - 1)
			if t == 2:
				leq[i] = min(leq[i], v - 1)
	imp = any((geq[i] > leq[i] for i in range(n)))
	if imp:
		ans = -1
	else:
		src = 2 * n + n * n
		tgt = 2 * n + n * n + 1
		G = MCFP()
		for i in range(n):
			G.add(src, i, 1, 0)
		for i in range(n):
			for j in range(geq[i], leq[i] + 1):
				G.add(i, j + n, 1, 0)
		for i in range(n):
			for j in range(n):
				G.add(i + n, 2 * n + i * n + j, 1, 0)
				G.add(2 * n + i * n + j, tgt, 1, 2 * j + 1)
		(_, ans) = G.solve(src, tgt)
	print(ans)
	return
main()


import atexit
import io
import sys
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

class Arista:

	def __init__(self, salida, llegada, capacidad, flujo, costo, indice):
		self.salida = salida
		self.llegada = llegada
		self.capacidad = capacidad
		self.flujo = flujo
		self.costo = costo
		self.indice = indice

	def __str__(self):
		s = ''
		s = s + 'salida =' + str(self.salida) + '\n'
		s = s + 'llegada =' + str(self.llegada) + '\n'
		s = s + 'capacidad =' + str(self.capacidad) + '\n'
		s = s + 'flujo =' + str(self.flujo) + '\n'
		s = s + 'costo =' + str(self.costo) + '\n'
		s = s + 'indice =' + str(self.indice) + '\n'
		s = s + '------------'
		return s

class Red:

	def __init__(self, s, t):
		self.lista_aristas = []
		self.lista_adyacencia = {}
		self.vertices = set()
		self.fuente = s
		self.sumidero = t

	def agregar_vertice(self, vertice):
		self.vertices.add(vertice)

	def agregar_arista(self, arista):
		self.vertices.add(arista.salida)
		self.vertices.add(arista.llegada)
		self.lista_aristas.append(arista)
		if arista.salida not in self.lista_adyacencia:
			self.lista_adyacencia[arista.salida] = set()
		self.lista_adyacencia[arista.salida].add(arista.indice)

	def agregar_lista_aristas(self, lista_aristas):
		for arista in lista_aristas:
			self.agregar_arista(arista)

	def cantidad_de_vertices(self):
		return len(self.vertices)

	def vecinos(self, vertice):
		if vertice not in self.lista_adyacencia:
			return set()
		else:
			return self.lista_adyacencia[vertice]

	def buscar_valor_critico(self, padre):
		INFINITO = 1000000000
		valor_critico = INFINITO
		actual = self.sumidero
		while actual != self.fuente:
			arista_camino = self.lista_aristas[padre[actual]]
			valor_critico = min(valor_critico, arista_camino.capacidad - arista_camino.flujo)
			actual = arista_camino.salida
		return valor_critico

	def actualizar_camino(self, padre, valor_critico):
		actual = self.sumidero
		costo_actual = 0
		while actual != self.fuente:
			self.lista_aristas[padre[actual]].flujo += valor_critico
			self.lista_aristas[padre[actual] ^ 1].flujo -= valor_critico
			costo_actual += valor_critico * self.lista_aristas[padre[actual]].costo
			actual = self.lista_aristas[padre[actual]].salida
		return (costo_actual, True)

	def camino_de_aumento(self):
		INFINITO = 1000000000
		distancia = {v: INFINITO for v in self.vertices}
		padre = {v: -1 for v in self.vertices}
		distancia[self.fuente] = 0
		(capa_actual, capa_nueva) = (set([self.fuente]), set())
		while capa_actual:
			for v in capa_actual:
				for arista_indice in self.vecinos(v):
					arista = self.lista_aristas[arista_indice]
					if arista.flujo < arista.capacidad and distancia[arista.salida] + arista.costo < distancia[arista.llegada]:
						distancia[arista.llegada] = distancia[arista.salida] + arista.costo
						padre[arista.llegada] = arista.indice
						capa_nueva.add(arista.llegada)
			capa_actual = set()
			(capa_actual, capa_nueva) = (capa_nueva, capa_actual)
		if distancia[self.sumidero] < INFINITO:
			valor_critico = self.buscar_valor_critico(padre)
			(costo_actual, hay_camino) = self.actualizar_camino(padre, valor_critico)
			return (valor_critico, costo_actual, hay_camino)
		else:
			return (-1, -1, False)

	def max_flow_min_cost(self):
		flujo_total = 0
		costo_total = 0
		hay_camino = True
		while hay_camino:
			(flujo_actual, costo_actual, hay_camino) = self.camino_de_aumento()
			if hay_camino:
				flujo_total += flujo_actual
				costo_total += costo_actual
		return (flujo_total, costo_total)
INFINITO = 10000000000000
(n, q) = map(int, input().split())
maxi = [n for i in range(n)]
mini = [1 for i in range(n)]
R = Red(0, 2 * n + 1)
prohibidos = {i: set() for i in range(n)}
for i in range(n):
	for k in range(n + 1):
		R.agregar_arista(Arista(R.fuente, i + 1, 1, 0, 2 * k + 1, len(R.lista_aristas)))
		R.agregar_arista(Arista(i + 1, R.fuente, 0, 0, -2 * k - 1, len(R.lista_aristas)))
for j in range(n):
	R.agregar_arista(Arista(n + j + 1, R.sumidero, 1, 0, 0, len(R.lista_aristas)))
	R.agregar_arista(Arista(R.sumidero, n + j + 1, 0, 0, 0, len(R.lista_aristas)))
for z in range(q):
	(t, l, r, v) = map(int, input().split())
	if t == 1:
		for i in range(v - 1):
			for j in range(l, r + 1):
				prohibidos[i].add(j)
	else:
		for i in range(v, n):
			for j in range(l, r + 1):
				prohibidos[i].add(j)
for i in range(n):
	for j in range(mini[i], maxi[i] + 1):
		if j not in prohibidos[i]:
			R.agregar_arista(Arista(i + 1, n + j, 1, 0, 0, len(R.lista_aristas)))
			R.agregar_arista(Arista(n + j, i + 1, 0, 0, 0, len(R.lista_aristas)))
(flujo_total, costo_total) = R.max_flow_min_cost()
if flujo_total < n:
	print('-1')
else:
	print(costo_total)