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

Difficulty: interview

Starter code:

Solutions:
#~ # MAGIC CODEFORCES PYTHON FAST IO
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())
#~ # END OF MAGIC CODEFORCES PYTHON FAST IO

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(): 
	## Representacion de una Red de flujo ##
	def __init__(self,s,t): # Crea una red vacio
		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
		#~ for iteracion in range(len(self.vertices)-1):
			#~ for arista in self.lista_aristas:
				#~ 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_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:
			#~ for x in self.lista_aristas:
				#~ print(x)
			
			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 = list(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 = list(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()
#~ print(flujo_total,costo_total)
if flujo_total < n:
	print("-1")
else:
	print(costo_total)		
		

		
	
			
		




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(G)
        #print(leq, geq)
    print(ans)
    return

main()


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


import sys

def is_feasible(cnt,L,R):
	n = len(R)
	inter = [(L[i],R[i]) for i in range(n)]
	AUX = []
	feasible = True
	for x in range(n):
		for p in inter:
			if p[0] == x:
				AUX.append(p[1])
				
		while AUX and min(AUX) < x:
			AUX.remove(min(AUX))
		for quantity in range(cnt[x]):
			if AUX:
				AUX.remove(min(AUX))
			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

def is_feasible(cnt,L,R):
	n = len(R)
	inter = [(L[i],R[i]) for i in range(n)]
	AUX = []
	feasible = True
	for x in range(n):
		for p in inter:
			if p[0] == x:
				AUX.append(p[1])
				
		while AUX and min(AUX) < x:
			AUX.remove(min(AUX))
		for quantity in range(cnt[x]):
			if AUX:
				AUX.remove(min(AUX))
			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 
					if had_pair:
						break
			if had_pair:
				break
	
	ans = sum([cnt[x]*cnt[x] for x in range(n)])
	print(ans)
	
					
			
			
		
		
		
			
			
			
		


import sys

def is_feasible(cnt,L,R):
	n = len(R)
	inter = [(L[i],R[i]) for i in range(n)]
	AUX = []
	feasible = True
	for x in range(n):
		for p in inter:
			if p[0] == x:
				AUX.append(p[1])
				
		while AUX and min(AUX) < x:
			AUX.remove(min(AUX))
		for quantity in range(cnt[x]):
			if AUX:
				AUX.remove(min(AUX))
			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-1,-1,-1):
			for y in range(n-1,-1,-1):
				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
from random import seed,shuffle

seed(25)

def is_feasible(cnt,L,R):
	n = len(R)
	inter = [(L[i],R[i]) for i in range(n)]
	AUX = []
	feasible = True
	for x in range(n):
		for p in inter:
			if p[0] == x:
				AUX.append(p[1])
		while AUX and min(AUX) < x:
			AUX.remove(min(AUX))
		for quantity in range(cnt[x]):
			if AUX:
				AUX.remove(min(AUX))
			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
		AUX = list(range(n))
		shuffle(AUX)
		for x in AUX:
			AUX_2 = list(range(n))
			shuffle(AUX_2)
			for y in AUX_2:
				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

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
 
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:0 for x in range(n)}
	for y in range(n):
		for x in range(n):
			if cnt[x] == y:
				cnt[x] += 1
				if not is_feasible(cnt,L,R):
					cnt[x] -= 1 
	ans = sum([cnt[x]*cnt[x] for x in range(n)])
	print(ans)