Monster Generator
Description
You are playing a computer game fighting against monsters. To become the master in the game, you decide to train yourself today and in the following $m$ days using the monster generator.
The generator will generate $n$ monsters every day for training. Assume it is the $k$-th ($0\leq k\leq m$) day now, you need to assign $s_k$ health points (HP) before fighting against monsters. Then you need to beat all the $n$ monsters generated by the generator. You can fight against these monsters in an arbitrary order that you like. During the fight with the $i$-th monster, the player will lose $a_i+\Delta a_i\times k$ HP. And when the player finally beats the monster, the player will be awarded $b_i+\Delta b_i\times k$ HP. Note that when HP becomes negative ($< 0$), the training will fail, so never let this happen. Note that no matter how many HP you have, you still need to reassign your initial HP in the beginning of the next day's training.
The less initial HP you need, the more skilled you are. What's the minimum possible amount of total initial HP $s_0+s_1+s_2+\dots+s_{m-1}+s_m$ that can be achieved?
The first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 100$, $0\leq m\leq 10^{18}$).
Each of the next $n$ lines contains four integers $a_i,\Delta a_i,b_i$ and $\Delta b_i$ ($1 \leq a_i,\Delta a_i,b_i,\Delta b_i \leq 10^{15}$), denoting a monster.
Print a single line containing an integer, denoting the minimum amount of total initial HP. Note that the answer may be extremely large, so please print it modulo $2^{64}$ instead.
Input
The first line of the input contains two integers $n$ and $m$ ($1 \leq n \leq 100$, $0\leq m\leq 10^{18}$).
Each of the next $n$ lines contains four integers $a_i,\Delta a_i,b_i$ and $\Delta b_i$ ($1 \leq a_i,\Delta a_i,b_i,\Delta b_i \leq 10^{15}$), denoting a monster.
Output
Print a single line containing an integer, denoting the minimum amount of total initial HP. Note that the answer may be extremely large, so please print it modulo $2^{64}$ instead.
3 5
3 1 5 2
4 2 1 3
1 9 100 1
113