당신은 피라미드를 새로 짓기에 적합한 가장 넓은 부지를 찾아 달라는 요청을 받았다.

작업 수행을 위해 먼저 땅 전체를 M×N 크기의 정사각형 격자로 나누어 측량해 두었다.

피라미드를 짓는 영역은 이 격자에 평행한 정사각형 형태여야 한다.

조사한 바에 따르면 이 땅에는 P개의 장애물이 존재하는데, 이들은 격자에 평행한 직사각형 형태이며 일부 영역이 다른 장애물과 겹칠 수도 있다.

피라미드를 지으려면 피라미드가 차지하는 모든 칸에 장애물이 하나도 없어야 한다. i째 장애물을 제거하는 데 드는 비용은 Ci로 표현된다.

한 장애물은 이 비용을 모두 들여서 완전히 제거하는 것만 가능하며 장애물의 일부 영역만을 부분적으로 제거할 수는 없다. 또한 한 장애물을 제거하더라도 그 장애물과 겹치는 영역이 존재하는 다른 장애물은 영향을 받지 않는다.

땅의 크기인 M과 N, P개의 장애물들의 위치와 이들 각각의 제거 비용, 내게 있는 자금 B를 입력 받아서 이 땅에서 이 자금 한도로 만들 수 있는 피라미드의 가장 큰 크기를 구하는 프로그램을 작성하시오.

피라미드 부지(Pyramid Base) timer 5s memory 256MB

피라미드 부지(Pyramid Base) 5s 256MB