小明同学在参加一场考试,考试时间 2 个小时。试卷上一共有 n 道题目,小明要在规定时间内,完成一定数量的题目。 考试中不限制试题作答顺序,对于 i 第道题目,小明有三种不同的策略可以选择: (1)直接跳过这道题目,不花费时间,本题得0分。 (2)只做一部分题目,花费 pi 分钟的时间,本题可以得到 ai 分。 (3)做完整个题目,花费 qi 分钟的时间,本题可以得到 bi 分。 小明想知道,他最多能得到多少分。 数据范围: , ,
输入描述:
第一行输入一个n数表示题目的数量。接下来n行,每行四个数p_i,a_i,q_i,b_i。


输出描述:
输出一个数,小明的最高得分。
示例1

输入

4
20 20 100 60
50 30 80 55
100 60 110 88
5 3 10 6

输出

94
加载中...