#P18403. Monster Generator

Monster Generator

Monster Generator

你正在玩一款与怪物战斗的电脑游戏。为了成为游戏中的高手,你决定从今天开始,使用怪物生成器训练,并在接下来的 mm 天继续训练。

生成器每天产生 nn 只怪物。假设现在是第 kk 天(0≤k≤m0\le k\le m),你需要在战斗前设置初始生命值 sks_k,随后以任意顺序击败当天生成的全部 nn 只怪物。

与第 ii 只怪物战斗时,你会先失去 ai+Δai⋅ka_i+\Delta a_i\cdot k 点生命值;最终击败它后,再获得 bi+Δbi⋅kb_i+\Delta b_i\cdot k 点生命值作为奖励。

只要生命值变为负数(小于 0),当天训练就会失败。生命值恰好等于 0 是允许的。 即使击败怪物后会获得奖励,也不能在此前扣除生命值时变成负数。

无论上一天结束时还剩下多少生命值,每天开始训练时都必须重新设置当天的初始生命值。

需要的初始生命值越少,你就越熟练。请问总初始生命值

s0+s1+s2+⋯+sm−1+sms_0+s_1+s_2+\cdots+s_{m-1}+s_m

最少可以是多少?

输入格式

第一行包含两个整数 n,mn,m(1≤n≤1001\le n\le100,0≤m≤10180\le m\le10^{18})。今天是第 0 天,因此总共训练 m+1m+1 天。

接下来 nn 行,每行包含四个整数 ai,Δai,bi,Δbia_i,\Delta a_i,b_i,\Delta b_i(1≤ai,Δai,bi,Δbi≤10151\le a_i,\Delta a_i,b_i,\Delta b_i\le10^{15}),描述一只怪物。

输入只有一组数据。

输出格式

输出一行一个整数,表示最小总初始生命值对 2642^{64} 取模的结果。以非负十进制整数输出。

样例

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

帮助理解的说明

样例中,第 0 至第 5 天各自需要的最少初始生命值依次为 1,7,15,23,30,371,7,15,23,30,37,总和为 113113。各天可以选择不同的战斗顺序,上一天的剩余生命值不带到下一天。