I. Exercise
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are participating in a programming contest. There are $$$n$$$ problems in total. The $$$i$$$-th problem has the following attributes:

  1. $$$a_i$$$: you gain $$$a_i$$$ points for solving this problem;
  2. $$$t_i$$$: it takes $$$t_i$$$ units of time to solve this problem;
  3. $$$b_i$$$: you lose $$$b_i$$$ points for every unit of time that passes before you solve this problem.

Formally, if you solve the $$$i$$$-th problem at time $$$s$$$ (timed from the start of the contest), the actual score you get from this problem is $$$a_i - b_i \cdot s$$$.

The total duration of the contest is $$$T$$$. You can solve any number of problems in any order (you may choose not to solve some problems), but the total time consumed by all solved problems must not exceed $$$T$$$.

You need to maximize the total score you obtain.

Input

The first line contains two integers $$$n, T$$$ ($$$1 \le n \le 2000$$$, $$$1 \le T \le 2000$$$).

The next $$$n$$$ lines each contain three integers $$$a_i, b_i, t_i$$$ ($$$0 \le a_i, b_i \le 10^6$$$, $$$1 \le t_i \le T$$$).

Output

Print a single integer on a line, representing the maximum possible total score.

Example
Input
3 10
10 1 3
20 2 5
30 3 4
Output
21
Note

If you solve problem 3 first and then problem 1, your score will be $$$(30-4\times 3)+(10-(4+3)\times 1)=21$$$.