🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 2

소민이는 어느 날 자기 방 창문의 방충망에 구멍이 뚫려 있다는 사실을 알게 되었다. 모기가 방에 들어오는 게 싫은 소민이는 방충망을 보수하려고 한다. 소민이가 가진 방충망 보수 스티커는 한 장뿐이고, 그 모양은 가로와 세로의 길이가 같은 정사각형이다. 소민이는 이 스티커 한 장으로 최대한 많은 구멍을 빈틈없이 가리려고 한다.

예를 들어 굵은 테두리로 표시된 직사각형들에 구멍이 뚫려 있다고 하자. 빨간색 정사각형 크기의 방충망 보수 스티커가 있을 때 빈틈없이 가릴 수 있는 구멍은 최대 4개이다. 빈틈없이 최대한 많은 구멍을 가릴 수 있는 스티커의 위치는 하나로 정해지지 않을 수 있다.

방충망 보수 스티커를 잘 붙였을 때 빈틈없이 가릴 수 있는 구멍 개수의 최댓값을 구해 보자.

첫째 줄에 방충망 보수 스티커의 한 변의 길이 L이 주어진다. L은 정수이다. (1 ≤ L ≤ 1,000,000)

둘째 줄에 구멍의 개수 K가 주어진다. (1 ≤ K ≤ 100,000)

다음 K개의 줄에 구멍의 위치 좌표 (y1, x1, y2, x2)가 한 줄에 하나씩 주어진다. (0 ≤ y1 < y2 ≤ 1,000,000, 0 ≤ x1 < x2 ≤ 1,000,000)

(y1, x1, y2, x2)에서 (y1, x1)은 구멍의 왼쪽 아래 좌표, (y2, x2)는 구멍의 오른쪽 위 좌표이다. 주어지는 좌표는 모두 정수이다.

구멍은 일부 또는 전체가 겹쳐서 존재하지 않는다. 또한 연속된 구멍을 하나의 구멍으로 보지 않고 서로 독립된 구멍으로 본다.

첫째 줄에 방충망 보수 스티커로 빈틈없이 가릴 수 있는 구멍 개수의 최댓값을 출력한다.