문제
이 문제는 [2610 : 고기 잡이](KOI 2013 본선 중3) 문제의 N, L, M제한을 확장한 것이다.
[2610 : 고기 잡이]를 먼저 풀어볼 것을 권장한다.
지구 온난화로 인한 바닷물의 온도 상승,
그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고기의 수가 줄어들고 있다.
정부에서는 이 문제를 심각하게 생각하여,
물고기를 잡을 수 있는 곳과 여기서 고기잡이 배가 사용할 수 있는 그물의 폭에 제한을 두었다.
물고기는 바다 표면 근처에 살기 때문에, 그물의 높이는 중요하지 않다.
따라서 그물은 길이가 L 인 직선으로 생각할 수 있고, 물고기를 잡을 때,
그물은 한 변의 길이가 1 이상 정수인 직사각형 모양으로 치게 된다.
예를 들어, L =10 이라면, 칠 수 있는 그물의 모양은 1×4, 2×3, 3×2, 4×1 과 같이 4가지 형태의 직사각형이 된다.
고기를 잡을 수 있는 곳은 N×N 크기의 모눈종이 모양으로 되어 있다.
각 모눈에는 좌표가 주어지며, 가장 왼쪽 위 모눈이 (1,1)이고, 가장 오른쪽 아래 모눈이 (N,N)이다.
총 M마리의 물고기가 서로 다른 모눈 위에 한 마리씩 살고 있으며, 물고기는 움직이지 않는다.
고기잡이 배는 한 모눈 위에 위치를 잡고 자신의 오른쪽과 아래쪽으로 그물을 친다.
일단 그물을 치면, 그물 안, 그리고 그물에 걸친 물고기들을 잡을 수 있다.
예를들면, 다음 그림은 N = 7, L = 10 이고 M = 6 마리의 물고기가 (2,2), (2,4), (3,3), (5,6), (6,2), (7,4)에 살고 있을 때,
(2,2)에 놓인 고기잡이 배가 2×3 모양으로 그물을 친 예를 보이고 있다.
이 때 고기잡이 배는 총 3마리의 물고기를 잡을 수 있다.
고기를 잡을 수 있는 영역 밖으로 그물을 치는 경우는 없다.
입력
첫 번째 줄에는 모눈종이의 크기, 그물의 길이, 물고기의 수를 나타내는 세 개의 정수 N, L, M 이 하나의 공백을 두고 주어진다.
단, 2 ≤ N ≤ 100,000,000, 4 ≤ L ≤ 400,000,000, 1 ≤ M ≤ 500 이다. L은 L ≤ 4N 을 만족하는 짝수이다.
두 번째 줄부터 이후 M 개의 줄에는 각 물고기의 좌표가 하나의 공백을 두고 주어진다.
물고기의 좌표 순서는 무작위로 주어지며 하나의 2차원 좌표에 여러 마리의 물고기가 존재할 수 있다.
출력
예제
7 10 6
2 2
2 4
6 2
7 4
3 3
5 6
3
로그인해야 코드를 작성할 수 있어요.