分数: 450 点
问题陈述
有 N 食物,每种仅含有一种维生素 1, 2,和 3.
具体来说,吃 i-th 食物给你 A_i 维生素单位 V_i,和 C_i 卡路里。
Takahashi 可以选择其中的任何子集 N 食物只要总热量消耗不超过 X.
求这个的最大可能值:维生素中的最小摄入量 1, 2,和 3.
约束
- 1 \leq N \leq 5000
- 1 \leq X \leq 5000
- 1 \leq V_i \leq 3
- 1 \leq A_i \leq 2 \times 10^5
- 1 \leq C_i \leq X
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X V_1 A_1 C_1 V_2 A_2 C_2 \vdots V_N A_N C_N
输出
打印“维生素中最小摄入量”的最大可能值 1, 2,和 3“当消耗的总热量最多为 X.
示例输入 1
5 25 1 8 5 2 3 5 2 7 10 3 2 5 3 3 10
示例输出 1
3
如果食用,每种食物都会提供以下内容:
- 第一种食物: 8 维生素单位 1,和 5 卡路里
- 第二种食物: 3 维生素单位 2,和 5 卡路里
- 第三种食物: 7 维生素单位 2,和 10 卡路里
- 第四种食物: 2 维生素单位 3,和 5 卡路里
- 第五种食物: 3 维生素单位 3,和 10 卡路里
吃第 1、2、4 和 5 种食物会产生 8 维生素单位 1, 3 维生素单位 2, 5 维生素单位 3,和 25 卡路里。
在这种情况下,三种维生素摄入量的最小值是 3 (维生素 2).
不可能得到 4 或更多单位的每种维生素,但不得超过 25 卡路里,所以答案是 平面上的 3.
示例输入 2
2 5000 1 200000 1 2 200000 1
示例输出 2
0