|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||128 MB||12||9||9||75.000%|
You have been asked to find the largest affordable location for constructing a new pyramid. In order to help you decide, you have been provided with a survey of the available land which has been conveniently divided into an M by N grid of square cells. The base of the pyramid must be a square with sides parallel to those of the grid.
The survey has identified a set of P possibly overlapping obstacles, which are described as rectangles in the grid with sides parallel to those of the grid. In order to build the pyramid, all the cells covered by its base must be cleared of any obstacles. Removing the ith obstacle has a cost Ci. Whenever an obstacle is removed, it must be removed completely, that is, you cannot remove only part of an obstacle. Also, please note that removing an obstacle does not affect any other obstacles that overlap it.
Write a program that, given the dimensions M and N of the survey, the description of the P obstacles, the cost of removing each of the obstacles, and the budget B you have, finds the maximum possible side length of the base of the pyramid such that the total cost of removing obstacles does not exceed B.
Your program must read from the standard input the following data:
Your program must write to the standard output a single line containing one integer, the maximum possible side length of the base of the pyramid that can be prepared. If it is not possible to build any pyramid, your program should output the number 0.
6 9 42 5 4 1 6 3 12 3 6 5 6 9 1 3 3 8 24 3 8 6 9 21 5 1 6 2 20
The figure shows two possible locations for the pyramid's base, both having a side of length 4.