P1509 找啊找啊找朋友

题目描述

有 $n$ 个任务。完成第 $i$ 个任务需要消耗 $rmb_i$ 单位预算、$rp_i$ 单位点数和 $time_i$ 单位时间。 你共有 $m$ 单位预算和 $r$ 单位点数。请选择若干任务,使所选任务消耗的预算总和不超过 $m$,点数总和不超过 $r$。 你需要首先最大化完成的任务数量,并在完成任务数量最多的前提下,最小化完成这些任务所需的总时间。输出这个最小总时间。如果无法完成任何任务,则输出 $0$。

输入格式

第一行包含一个整数 $n$,表示任务数量。 接下来 $n$ 行,每行包含三个整数 $rmb_i,rp_i,time_i$,表示完成第 $i$ 个任务所需的预算、点数和时间。 最后一行包含两个整数 $m,r$,表示可用的预算和点数。

输出格式

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

说明/提示

对于 $20\%$ 的数据,$1 \le n \le 10$。 对于全部数据,$1 \le n,m,r \le 100$,$1 \le rmb_i,rp_i \le 100$,$1 \le time_i \le 1000$。