You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

水果滞销，帮帮我们

题目背景

小文的叔叔希望能够尽可能的挽回损失，但是由于水果很多，他无法找出一个最佳方案，在听说自己的侄子小文曾经学过算法后，他决定拜托小文来通过程序计算所能抢救的水果的最大总价值。

题目描述

小文的叔叔是一个水果批发商，最近由于市场行情不好，很多水果都滞销了，堆积在仓库里，小文的叔叔想了一些办法来抢救水果，但是每堆水果由于体积不同，需要$ti$天时间来装车运走，而水果会在$di$天时间后全部腐烂，每堆水果的价值为$vi$.

输入格式

第一行一个正整数n，表明有n堆水果 接着n行，每行四个数据 首先是一个字符串fruit_name，表示水果的名字 接着是三个正整数，t,d,v,含义由题面中给出

输出格式

输出最优方案下，所能抢救的水果的最大总价值

样例 #1

样例输入 #1

3
apple 5 6 1
pear 3 3 5
pineapple 4 4 2

样例输出 #1

5

提示

数据范围
n<=100,len(fruit_name)<=40
t<=20,d<=2000,v<=50