实验室的金属块

题目描述

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

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

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

输入格式

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

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

输出格式

这个最大体积是多少？

样例输入 #1

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

样例输出 #1

107730

数据范围

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

知识点与难度

本题涉及的知识点从属于 GESP五级（二分答案、二分基础），难度等级：⭐⭐⭐。

测试点分布