配点 : 600 点
問題文
N 饮水机和 1 有两个空杯子。 PCT 您想在这个玻璃杯中装满尽可能多的水。
給水機 i\,(1 \leq i \leq N) 是时间 S_i 到时间 只能使用 T_i 。另外,1 每秒供水量为 A_i 储存的水量(以升为单位)为 A_i\times B_i 升。也就是说,总共 供水时间不能超过 B_i 秒。
如果你行为得当,你能在一个玻璃杯里倒多少升水?然而,与此同时 2 您不能从多个饮水机向玻璃杯装水。
制約
- 1 \leq N \leq 500
- 1 \leq S_i < T_i \leq 10^9
- 1 \leq A_i,B_i \leq 10^9
- 所有输入均为整数
入力
输入将以以下格式从标准输入给出。
N S_1 T_1 A_1 B_1 S_2 T_2 A_2 B_2 \vdots S_N T_N A_N B_N
出力
打印答案。 它是按此顺序连接的
入力例 1
3 1 6 1 2 2 4 3 1 2 4 2 1
出力例 1
7
時刻 1 到时间 只能使用 2 最多 1 第二个是饮水机 1 到 1 将升水倒入玻璃杯中。
時刻 2 到时间 只能使用 3 最多 1 第二个是饮水机 2 到 3 将升水倒入玻璃杯中。
時刻 3 到时间 只能使用 4 最多 1 第二个是饮水机 3 到 2 将升水倒入玻璃杯中。
時刻 4 到时间 只能使用 5 最多 1 第二个是饮水机 1 到 1 将升水倒入玻璃杯中。
如果你这样做的话,总共 7 您可以在玻璃杯中装满升水。 除以
入力例 2
1 1 100 100 3
出力例 2
300
入力例 3
4 1 3 4 5 1 4 3 4 3 4 5 2 4 6 2 2
出力例 3
17