1460번 - 진욱이의 농장

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

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

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

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

첫째 줄에 두 정수 농장의 크기 N과 씨앗을 뿌린 횟수 M이 주어진다.

둘째 줄부터 M개의 줄에는 씨를 뿌린 방법이 주어진다. 각각의 줄은 네 정수 X, Y, L, F로 이루어져 있다.

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

• 1 ≤ N ≤ 1,000
• 1 ≤ M ≤ 50
• 0 ≤ X, Y ≤ N-1
• 1 ≤ L ≤ N
• 1 ≤ X+L, Y+L ≤ N
• 0 ≤ F ≤ 7