A. Did he drop any good loot?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Слава играет в очень крутую RPG. Он зачистил подземелье, выбил n крутых артефактов и теперь хочет как можно выгоднее их продать. Для каждого артефакта Слава знает его цену pi и массу wi. Слава не может унести на продажу артефакты с суммарной массой более m. Но Слава может активировать некоторые артефакты. При активации i-ый артефакт увеличивает Славину силу и прибавляет к пределу переносимой массы di (активированные артефакты не исчезают, их стоимость и масса не изменяются, их также можно потом продать). Одновременно Слава может иметь активированными не более 2 артефактов.

Более формально, Слава хочет выбрать множество артефактов с максимальной суммарной стоимостью среди всех корректных множеств. Множество артефактов i1, i2, ..., ik (k ≤ n) называется корректным, если wi1 + wi2 + ... + wik ≤ m + s, где s — эффект от активации артефактов: s = dj1 + dj2, если Слава активировал артефакты j1 и j2 (j1 ≠ j2), s = dj — если он активировал только артефакт j, и s = 0, если Слава не активировал артефакты (j1, j2 и j обязаны входить в множество взятых артефактов i1, i2, ..., ik).

Входные данные

В первой строке содержатся два целых числа через пробел: n и m (1 ≤ n ≤ 104, 1 ≤ m ≤ 500) — количество артефактов и максимальная масса, которую способен унести Слава, соответственно.

Далее в n строках содержатся по три целых числа через пробел: pi, wi и di (1 ≤ pi ≤ 105, 1 ≤ wi ≤ 100, 0 ≤ di ≤ 100) — соответственно стоимость артефакта, его масса, а также прибавка к пределу переносимой массы, которую он даёт при активации.

Выходные данные

Выведите единственное целое число — максимальную суммарную стоимость унесённых Славой артефактов.

Примеры
Входные данные
5 10
1 5 3
2 4 0
3 2 2
4 1 4
5 3 1
Выходные данные
15
Входные данные
3 10
100 100 20
200 80 30
300 60 40
Выходные данные
0
Примечание

В первом тесте Слава не может просто так взять все артефакты — он может унести только массу до 10, а суммарная масса артефактов — 15. Поэтому Слава активирует артефакты 1 и 4, после чего его предел переносимой массы становится равным 10 + 3 + 4 = 17 (Слава также мог активировать любую пару артефактов, дающих в сумме прибавку 5 или более).

Во втором тесте Слава не может унести никакие артефакты — ни с активацией некоторых, ни без оной.