Степан повернувся з ярмарку настільних ігор. Він приніс додому ~N~ ігор. Перш ніж грати в гру, необхідно вивчити її правила. Вивчення правил ~i~-ї гри займає ~P_i~ хвилин. Після вивчення правил можна грати в гру. Гра в ~i~-ту гру займає ~T_i~ хвилин. Кожна гра також має свій власний рейтинг ~R_i~.

У найближчі дні Степан планує витратити щонайбільше D хвилин на настільні ігри. Який максимальний рейтинг зможе отримати Степан?. У кожну гру можна грати довільну кількість разів.

Обмеження

• ~1 \le N,D \le 5000~
• ~0 \le P_i \le 5000~
• ~1 \le T_i \le 5000~
• ~1 \le R_i \le 10^9~

Input

Перший рядок містить цілі числа ~N~ та ~D~ - кількість ігор та час, запланований на гру.

Далі ідуть ~N~ рядків, які містить цілі числа ~P_i~, ~T_i~ та ~R_i~ - час, необхідний для вивчення правил, час, необхідний для гри, та рейтинг ~i~-ї гри.

Output

Вивести максимальний прогнозований рейтинг Степана.

Scoring

• 15 балів при ~N~ = 1
• 25 балів при ~N \le 10~
• 25 балів при ~P_i = 0~
• 35 балів без додаткових обмежень

Sample Input 1

3 10
2 3 5
5 1 5
3 2 5

Sample Output 1

25

Sample Input 2

4 13
0 6 5
0 3 4
0 2 3
0 4 4

Sample Output 2

19

Sample Input 3

3 10
1 1 1
3 2 3
2 3 5

Sample Output 3

11