#1323. 找啊找啊找朋友

找啊找啊找朋友

题目描述

有 nn 个任务。完成第 ii 个任务需要消耗 rmbirmb_i 单位预算、rpirp_i 单位点数和 timeitime_i 单位时间。

你共有 mm 单位预算和 rr 单位点数。请选择若干任务,使所选任务消耗的预算总和不超过 mm,点数总和不超过 rr。

你需要首先最大化完成的任务数量,并在完成任务数量最多的前提下,最小化完成这些任务所需的总时间。输出这个最小总时间。如果无法完成任何任务,则输出 00。

输入格式

第一行包含一个整数 nn,表示任务数量。

接下来 nn 行,每行包含三个整数 rmbi,rpi,timeirmb_i,rp_i,time_i,表示完成第 ii 个任务所需的预算、点数和时间。

最后一行包含两个整数 m,rm,r,表示可用的预算和点数。

输出格式

输出一个整数,表示在完成任务数量最多的前提下,所需的最小总时间。

样例

4
1 2 5
2 1 6
2 2 2
2 2 3
5 5
13

题目来源:洛谷 P1509