Hide

Problem D
Moving Day

It’s that time of the year when students head back to school, which will usually involve moving lots of stuff, and packing lots of that stuff into boxes. However, before we go through that effort, it would be nice to know whether the boxes we have are the right size!

A box has three dimensions, l, w, and h, and a box’s volume v is simply lwh. We have many small items to pack, and we don’t care about their exact geometry: we know that, as long as a box has a volume of, at least, V, we will be able to pack all those items into that single box. So, given a box i, and its volume vi, then the difference di=viV can tell us whether the box is big enough or not to pack all the items. If di is greater than or equal to zero, the box is big enough; otherwise, the box is too small.

So, we want to answer a simple question: given multiple boxes, is the largest box (by volume) large enough to store all our items? For example, suppose V=10 and we have three boxes, A, B, and C, with dimensions (1,1,2), (2,2,2), and (3,2,1), respectively. Their volumes will be vA=2, vB=8, and vC=6, which means the largest box is B. Unfortunately, dB=vBV=810=2, which means our largest box is not large enough.

On the other hand, suppose V=980, and we had four boxes, W, X, Y, and Z with dimensions (10,10,10), (10,5,2), (5,3,2), and (90,5,2), respectively. Their volumes will be vW=1000, vX=100, vY=30 and vZ=900, making W the largest box and, since dW=vWV=1000980=20, that means W is big enough for all our items.

Input

The input specifies a set of boxes. It begins with a line containing two integers: n (1n100), specifying the number of boxes, and V, as defined above. The remaining input is composed of n lines, each specifying one box. Each line contains the dimensions l, w, and h for the box. You may assume that 1l,w,h,V<232. You may also assume that, for any given box i, its volume vi will always be less than 232

Output

The output is a single integer: the value of di for the largest box by volume.

Sample Input 1 Sample Output 1
3 10
1 1 2
2 2 2
3 2 1
-2
Sample Input 2 Sample Output 2
3 30
1 1 1
5 2 3
5 2 1
0
Sample Input 3 Sample Output 3
4 980
10 10 10
10 5 2
5 3 2
90 5 2
20
Hide

Please log in to submit a solution to this problem

Log in