题目描述

实验室购买了 $n$ 种金属材料，每种一根，需要把这些金属材料切割后，装到 $k$ 个罐子里面保存，每个罐子只能装一种金属，金属可以有剩余。

现在需要使用机器把金属切割成相同的体积，切割成的体积越大越好。

请帮忙计算这个最大体积是多少？

输入格式

第一行输入两个整数 $n$ 和 $k$。

接下来 $n$ 行，每行四个正整数，$a$、$b$、$c$，代表金属的长宽高，再输入一个整数 $z$，每种金属不能超过 $z$ 个罐子。

输出格式

这个最大体积是多少？（题目保证有解）

10 8
87 48 52 44
49 99 69 37
94 31 33 69
7 39 24 5
7 30 64 12
49 40 90 74
9 100 95 3
27 95 42 25
18 7 58 20
64 69 35 61

107730

提示

数据范围与提示：

对于 $100\%$ 的数据，有 $1 \le n \le 10^5,1 \le k \le 10^8,1 \le a,b,c \le 100$。