Problem 2: Indraneel's Pyramid, (K Narayan Kumar, CMI)
Indraneel would like a build a pyramid of wooden blocks. A pyramid is built by placing a square block, say N cms by N cms, at the base, place another square block N-1 cms by N-1 cms on top of that, a square block of N-2 cms by N-2 cms on top of that and so on, ending with a 1 cm by 1 cm block on top. The height of such a pyramid is N.
Indraneel has with him M rectangular blocks of wood. He is willing to shape them into square blocks. His only cutting tool is a shaver that can be used to shave off the wood from any edge to reduce its length. This means that he can never get two square blocks from a single rectangular block.
For example, suppose the dimensions of the rectangular blocks available with Indraneel are 8×8, 2×8, 2×1 and 2×2. Then, he can build a pyramid of height 3 (the 2×1 block can be shaved to give a 1×1 block, and the 8×8 block can be shaved down to a 3×3 block.)
Given the dimensions of the blocks available, your task is determine the height of the tallest pyramid that Indraneel can build.
The first line of the input contains a single integer M indicating the number of blocks of wood available. This is followed by M lines of input (lines 2, 3,...,M+1) each containing the description of a block. A block is described by two integers i and j indicating the lengths of the two sides of the block. No block is longer or wider than 1000000 cms.
A single line with a single integer indicating the height of the tallest pyramid that Indraneel can build.
You may assume that M ≤ 1000000. Recall that all block dimensions are bounded by 1000000 cms.
Here is the sample input and output corresponding to the example discussed above.
4 8 8 2 8 2 1 2 2
|CPU Timelimit:||3 seconds|