정부는 참나무 숲 한가운데에 관광객들을 위한 산책로를 건설할 계획입니다.

숲에는 N 그루의 참나무가 있고, 해당 참나무들의 위치는 평면 위에서의 격자점으로 나타낼 수 있습니다.

산책로는 측면이 축과 평행한 직사각형으로 이루어집니다.

산책로를 이루는 직사각형의 측면이 참나무의 위치와 교차하는 경우, 이러한 나무는 베어야 합니다.

직사각형 안에 있는 나무는 자를 필요가 없습니다.

산림청 장관은 관광부 장관에게 관광객을 끌어들일 만큼 매력적인 직사각형 산책로 목록을 제공하라고 지시했습니다.

산림청 장관은 열정적인 자연 애호가이기 때문에 가장 적은 양의 참나무가 베어져야 하는 산책로를 선택할 계획입니다.

목록으로 주어진 산책로들에 대해서 각 산책로마다 최소로 베어야하는 참나무의 수를 출력하는 프로그램을 작성합시다.

산책로 timer 1s memory 128MB

산책로 1s 128MB