← 返回题目列表

AtCoder · abc390_e

E. 维生素平衡

中文机器翻译题面 查看原题

分数: 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