시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 20 8 6 42.857%

문제

진욱이는 N*N 크기의 정사각형 농장을 가지고 있다. 농장은 1*1크기의 칸으로 나누어져 있고, 각 칸은 한 종류의 과일이 심어져 있다. 가장 처음에 농장에는 모두 0번 과일만 심어져 있다. 

진욱이는 총 씨앗을 M번 뿌리려고 한다. 이 때, 씨앗을 뿌리는 방벙은 네 정수 X, Y, L, F로 나타낼 수 있다. 여기서 (X, Y)는 정사각형의 왼쪽 위 모서리 좌표이고, L은 정사각형 변의 길이, F는 씨앗의 종류이다. 만약, 씨를 이미 뿌린 곳에 또 뿌리는 경우에는, 원래 심어져있던 씨가 없어지고, 새로운 씨가 심어지게 된다. 가장 왼쪽 위 모서리의 좌표는 (0, 0)이다.

진욱이는 군대에 입대하기 전에 준규에게 농장의 일부를 주고 가려고 한다. 준규가 정사각형 모양으로 농장을 가져갈 수 있다. 이 때, 정사각형에 포함된 과일의 종류는 최대 두 종류이어야 하고, 0번 과일은 가져갈 수 없다.

준규가 가져갈 수 있는 가장 넓은 농장의 넓이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 농장의 크기 N(1 ≤ N ≤ 1,000)과 씨앗을 뿌린 횟수 M(1 ≤ M ≤ 50)이 주어진다.

둘째 줄부터 M개의 줄에는 씨를 뿌린 방법이 주어진다. 각각의 줄은 X, Y, L, F로 이루어져 있다. (0 ≤ X, Y ≤ N-1, 1 ≤ X+L, Y+L ≤ N, 0 ≤ F ≤ 7)

출력

준규가 가져갈 수 있는 가장 넓은 정사각형의 넓이를 출력한다.

예제 입력

7 3
0 0 7 7
2 2 4 1
3 5 1 5

예제 출력

25

힌트

출처