Hide

Problem B
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 $l\cdot w \cdot h$. 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, $\mathbf{V}$, we will be able to pack all those items into that single box. So, given a box $i$, and its volume $v_ i$, then the difference $d_ i=v_ i-\mathbf{V}$ can tell us whether the box is big enough or not to pack all the items. If $d_ i$ 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 $\mathbf{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 $v_ A=2$, $v_ B=8$, and $v_ C=6$, which means the largest box is $B$. Unfortunately, $d_ B=v_ B-\mathbf{V}=8-10=-2$, which means our largest box is not large enough.

On the other hand, suppose $\mathbf{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 $v_ W=1\, 000$, $v_ X=100$, $v_ Y=30$ and $v_ Z=900$, making $W$ the largest box and, since $d_ W=v_ W-\mathbf{V}=1\, 000-980=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$ ($1 \le n \le 100$), specifying the number of boxes, and $\mathbf{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 $1 \leqslant l, w, h, \mathbf{V} < 2^{32}$. You may also assume that, for any given box $i$, its volume $v_ i$ will always be less than $2^{32}$

Output

The output is a single integer: the value of $d_ i$ 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

Please log in to submit a solution to this problem

Log in