题目描述

山洞中有 $n$ 种草药，第 $i$ 种草药的采摘时间为 $t_i$，价值为 $v_i$，数量信息为 $s_i$：

• $s_i = 0$ 表示有无限多株（完全背包）
• $s_i = -1$ 表示只有一株（01背包）
• $s_i > 0$ 表示有 $s_i$ 株（多重背包）

给定总时间 $T$，求能采到的草药最大总价值。

输入格式

第一行两个整数 $n, T$。

接下来 $n$ 行，每行三个整数 $t_i, v_i, s_i$。

输出格式

输出一个整数，表示最大总价值。

输入输出样例 #1

输入 #1

样例

输入

4 10

输出

2 3 -1
3 4 0
4 5 2
5 6 -1

输出 #1

15

说明/提示

数据范围

• $1 \le n \le 100$
• $1 \le T \le 1000$
• $1 \le t_i, v_i \le 100$
• $-1 \le s_i \le 100$