问题1113--ZHAN与开封菜

1113: ZHAN与开封菜

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 64 MB

提交

题目描述

    众所周知,ZHAN是一名KaiFengCai美食专家,他对KFC的每一种食品都了如指掌,熟悉它们的重量、美味度和价格。

    每当ZHAN在KFC就餐时,至少要吃重量为aa的食物才能吃饱,但是不能吃重量超过bb的食物,否则会因吃太饱而发胖。此外,他还会计算这顿饭中所有食物的美味度之和,作为满意度。

    现在,ZHAN拿着cc元钱走入了一家有nn种食物,且每种食物无限供应的KFC,准备进行自助点餐。他希望能找出一种点餐方案,使他能够在既不太饱也不太饿,并且不超出预算的前提下获得最高的满意度。ZHAN现在太饿了,脑子停止了思考,你能帮帮他吗?

输入

    第一行四个整数n,a,b,cn,a,b,c(1n100,1ab500,1c500)(1≤n≤100,1≤a≤b≤500,1≤c≤500),含义如上所述。

    接下来nn行,每行三个整数x,y,zx,y,z(1x,y,z500)(1≤x,y,z≤500),分别表示每种食品的重量、美味度和价格。

输出

    一个整数,表示能获得的最高的满意度。

    如果不存在既不太饱也不太饿,同时也不会超出支出预算的方案,则输出1−1

样例输入 Copy

2 7 9 4
5 7 2
2 3 1

样例输出 Copy

13

来源/分类