题目描述

徐老师做了一个奇怪的梦，他梦了到明天n支股票的价格。如果徐老师的梦在明天成为了现实，并且徐老师今天手里有m元钱，支持徐老师的你需要帮助他出谋划策，使他的财富实现最大化（假设一天内所有股票的价格不变）。

输入格式

输入第一行，包含两个正整数 n和m，n表示梦中的股票总数，m表示徐老师今天手中的全部金额。

1≤n≤30000 0≤m≤10000

接下来 n 行，每行三个整数，分别是xi，yi，zi，xi表示第i支股票的今日每股价格，yi表示该股票的明日每股价格，zi表示这支股票的限购总数，0表示不限购。

0<xi,yi≤${10}^7$，0≤zi≤1000

输出格式

输出一个整数

表示徐老师明天总资产的最大值。

样例

样例输入

1 2
1 2 1

样例输出

3