한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고기의 수가 줄어들고 있다. 정부에서는 이 문제를 심각 하게 생각하여, 물고기를 잡을 수 있는 곳과 여기서 고기잡이 배가 사용할 수 있는 그물의 폭에 제한을 두었다. 물고기는 바다 표면 근처에 살기 때문에, 그물의 높이는 중요하지 않다. 따라서 그물 은 길이가 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마리의 물고기를 잡을 수 있다. 고기를 잡을 수 있는 영역 밖 으로 그물을 치는 경우는 없다.
고기를 잡을 수 있는 영역, 물고기의 위치, 그물의 폭이 주어졌을 때 한 번의 그물치기로 잡을 수 있는 가장 많은 물고기의 마릿수를 구하는 프로그램을 작성하시오. 수행 시간은 1초를 넘을 수 없다. 부분점수는 없다.
입력 7 10 6 2 2 2 4 6 2 7 4 3 3 5 6 출력 3
출처:2013 koi 중등 지역본선 2/5대회 풀이