你正在玩一款对抗怪物的电脑游戏。为了成为游戏大师，你决定利用怪物生成器在今天以及接下来的 $m$ 天里进行训练。

生成器每天会生成 $n$ 只怪物供你训练。假设现在是第 $k$ 天（$0 \le k \le m$），你需要先分配 $s_k$ 点生命值（HP），然后击败生成器生成的全部 $n$ 只怪物。你可以以任意顺序与这些怪物战斗。在与第 $i$ 只怪物战斗时，玩家会损失 $a_i + \Delta a_i \times k$ 点 HP。当玩家最终击败该怪物时，会获得 $b_i + \Delta b_i \times k$ 点 HP。注意，当 HP 变为负数（$< 0$）时，训练就会失败，因此绝不能让这种情况发生。此外，无论你剩余多少 HP，在每一天训练开始时，你都需要重新分配初始 HP。

你需要的初始 HP 越少，说明你越熟练。请问 $s_0 + s_1 + s_2 + \dots + s_{m-1} + s_m$ 的最小值是多少？

输入格式

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 100$，$0 \le m \le 10^{18}$）。

接下来的 $n$ 行，每行包含四个整数 $a_i, \Delta a_i, b_i$ 和 $\Delta b_i$（$1 \le a_i, \Delta a_i, b_i, \Delta b_i \le 10^{15}$），表示一只怪物。

输出格式

输出一行一个整数，表示总初始 HP 的最小值。注意，答案可能非常大，请将其对 $2^{64}$ 取模后输出。

样例

样例输入 1

3 5
3 1 5 2
4 2 1 3
1 9 100 1

样例输出 1

113