🎵니가 싫어 싫어 너무 싫어 싫어 오지 마 내게 찝쩍대지마🎵 - 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)은 구멍의 오른쪽 위 좌표로 정의한다. 주어지는 좌표는 모두 정수이다.

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

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