시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB144413144.286%

문제

진욱이는 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

예제 입력 1

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

예제 출력 1

25

예제 입력 2

3 1
0 0 3 1

예제 출력 2

9

예제 입력 3

3 1
1 1 1 7

예제 출력 3

1

예제 입력 4

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

예제 출력 4

16

출처