You are given N building blocks each of which has a height H. weight W. You want to build a tower by stacking up blocks to reach a height of atleast K.
You should consider the strength for each block which indicates the maximum amount of total weight of the blocks that can be stacked above a while building the tower.
Given these constraints: you are required to find whether it is possible to construct a tower with a height of at least K. if it is possible to build the tower with a height of at least then find the maximum safety factor of the tower.
Note:
• You should return-1 if it is impossible to build a tower that satisfies the given constraints.
• The maximum safety factor of the tower is the amount of weight you can add to the top of the tower without exceeding any block's strength.
Input Format:
The first line of input contains a single integer N denoting the number of building blocks.
The next line of input contains a single integer K denoting the required height of the tower.
Each line i of the N subsequent lines (where 0 <=i<N) contains an integer describing Hi that denotes the height of block i.
| Sample Input | Sample Output | Explanation |
|---|---|---|
| 3 5 3 3 2 10 5 3 6 4 15 | 5 | Place block 1 upon block 3.Max safety:5 |
| 4 10 9 3 5 4 8 3 5 4 1 5 | -1 | It is not possible to arrange them |
| 4 10 9 3 5 4 4 3 5 4 1 5 10 5 | 2 | Block 3 in the lowermost layer block in the 2nd lower layer block 2 in the top layer .Max safety =2 |