题目描述

一个旅行者有一个最多能装 $M$ 公斤的背包，现在有 $N$ 种物品，它们的重量分别是 $w_1,w_2,...w_n$, 它们的价值分别为 $v_1,v_2,...,v_n$, 每种物品有 $m_1,m_2,...m_n$ 件，求旅行者能获得最大总价值。

输入格式

第一行：两个整数 $N,M$.

接下来 $M$ 行，每行三个整数 $w_i,v_i,m_i$,表示第 $i$ 种物品的重量、价值和数量。

输出格式

输出最大的价值。

样例1

输入

4 20
9 3 3
9 5 1
4 9 2
1 8 3

输出

47

数据规模与约定

对前 $20\%$ 的数据，$1\le m_i\le 50$。

对于 $100$ 的数据，$N≤50$，$1\le m_i\le 10^5$，$0\le v_i\le 1000$，$0≤w_i≤100$，$1≤M≤10^5$。