美食计划

Time Limit: 3000 MS

Memory Limit: 65535 KB

Description

有一天,Hdd去吃自助餐。那家餐馆有n种食物可供选择,每种食物分别由不同的厨师供应,由于厨师们水平有限,每分钟只能产生一定数量的食物。某一分钟生产出来的食物Hdd可以自由取用,但是如果他不在这一分钟吃掉,这些食物全部会被别人吃掉。而且厨师只有在固定时间才会上班。既然是自助餐,一定要吃饱,吃好,作为极品吃货的Hdd决定把这n种食物都吃够,他想让我们帮他算算如果他要实现自己的美食计划,他每分钟的食量至少要达到多少,当然Hdd每分钟可以吃多种食物。

Input

有多组输入数据,以文件尾结束。

每组数据以2个整数开始:N(1<=n<=100)表示有N种食物 ,T(1<=T<=1500)代表Hdd吃自助餐的时间。

后面接着n行,每行有4个整数,Fi,Vi,Si,Ei。Fi(0<=fi<=100,000)代表Hdd准备吃掉Fi个第i种食物,Vi(0<=Vi<=100,000)代表每分钟可以产生Vi个第i种食物,Si,Ei(1<=Si<=Ei<=t)代表这种食物从第Si分钟初开始供应,在第Ei分钟末结束供应。

Output


每组数据分别输出一行:Hdd每分钟的食量至少要达到多少才能吃够。如果Hdd怎么吃都无法吃够,输出-1。


Sample Input

3 4
100 50 1 2
100 50 1 2
100 100 4 4
3 4
100 50 1 2
100 50 2 3
100 100 3 3

Sample Output

100
150

Hint

None

Source

周宇哲

提交代码