P15067

烛光晚餐

难度 5 级 小学 动态规划入门 背包DP
讨论 统计 21通过 51提交 41.2%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

小明准备请小红去一家咖啡厅,共进烛光晚餐。小红高兴地和他一起去了咖啡厅。

小红说:“小明,你点菜吧。”小明看到菜单上有 N 道菜,每道菜的价格是 C_i。小明对每道菜的喜爱程度是 X_i,小红对每道菜的喜爱程度是 Y_i。(喜爱程度可能为负数)(小明:以我对她的了解,我给你的数据不会错的)

小明带了 V 元钱,他点的菜的总价格不能超过 V(小明:当然得我请客啦,显得我大方。)

小明希望让小红吃得开心,所以当然要让她的总喜爱程度尽量大。当然,小明也要考虑自己的感受,点的所有菜的总喜爱程度需要大于等于 0。(小明:要是我吃得不好,她看见我会难过的)

请你帮小明写一个程序,计算出他的总喜爱程度大于等于 0 的前提下,小红的喜爱程度的最大值。(小明:你的程序一定要靠谱啊,我得给她一个好印象)

输入

第一行,两个正整数 N,V。

之后 N 行,每行 3 个空格隔开的正整数 C_i,整数 X_i,Y_i。

输出

一行,一个正整数,表示他的总喜爱程度大于等于 0 的前提下,小红的喜爱程度的最大值。如果这个最大值小于 0,输出 -1.

样例

样例 1
输入
4 10
5 -1 3
2 2 2
11 -5 100
3 -3 10
输出
5

提示

对于 100\% 的数据,N\leq100,V\leq500,|X_i|\leq5,|Y_i|\leq10^3.

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交