D. Посылки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ярослав — владелец небольшой курьерской службы. Недавно он приобрел и внедрил новую систему обработки посылок. Каждая посылка представляет собой коробку, имеющую свой вес и прочность. Система устроена так, что внутри нее находится изначально пустая платформа, на которую можно ставить коробки по следующим правилам:

  • Если платформа пуста, коробка ставится непосредственно на платформу, в противном случае — на самую верхнюю коробку, находящуюся на платформе.
  • Суммарный вес всех коробок, находящихся на платформе, в любой момент времени не должен превышать прочности платформы S.
  • Прочность любой находящейся на платформе коробки в любой момент времени должна быть не меньше суммарного веса коробок, стоящих выше.

Снимать с платформы можно только самую верхнюю коробку.

На вход системе поступают n посылок, при этом i-я посылка поступает ровно в момент времени ini, ее вес и прочность равны wi и si соответственно. Каждая посылка имеет свою стоимость vi бурлей, однако, чтобы получить эту стоимость, системе необходимо выдать посылку ровно в момент времени outi, в противном случае Ярослав получит за нее 0 бурлей. Таким образом, любую посылку можно пропустить и не ставить на платформу, формально выдав ее в момент времени ini и не получив за нее ничего.

Любая операция в задаче выполняется мгновенно. Это означает, что в один и тот же момент времени можно совершить сразу несколько операций по приему и выдаче посылок, причем в любом порядке.

Обратите внимание, что посылка, выданная в момент времени outi, сразу же оказывается вне системы, и следующие действия, происходящие в этот же момент времени, производятся без ее учета.

Поскольку система очень сложна, а поступающих посылок очень много, Ярослав просит Вас сказать, какую максимальную сумму денег он может получить с помощью своей системы.

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

В первой строке входных данных содержатся два числа, разделенных пробелом n и S (1 ≤ n ≤ 500, 0 ≤ S ≤ 1000). Далее следует n строк, в i-й из этих строк содержатся пять чисел, разделенных пробелом: ini, outi, wi, si и vi (0 ≤ ini < outi < 2n, 0 ≤ wi, si ≤ 1000, 1 ≤ vi ≤ 106). Гарантируется, что для любых i и j (i ≠ j) либо ini ≠ inj, либо outi ≠ outj.

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

Выведите единственное число — максимальную сумму (в бурлях), которую может получить Ярослав.

Примеры
Входные данные
3 2
0 1 1 1 1
1 2 1 1 1
0 2 1 1 1
Выходные данные
3
Входные данные
5 5
0 6 1 2 1
1 2 1 1 1
1 3 1 1 1
3 6 2 1 2
4 5 1 1 1
Выходные данные
5
Примечание

Пояснение ко второму примеру (T — момент времени):

  • T = 0: Приходит первая посылка, ставим ее на пустую платформу.
  • T = 1: Приходят вторая и третья посылки, ставим третью на текущую верхнюю на платформе посылку (т.е. первую), затем вторую на третью. Теперь первая посылка держит вес w2 + w3 = 2, третья — w2 = 1.
  • T = 2: Выдаем вторую посылку, получая v2 = 1 бурль. Теперь первая посылка держит вес w3 = 1, третья — 0.
  • T = 3: Приходит четвертая посылка. Сначала выдаем третью посылку, получая v3 = 1 бурль. Теперь первая посылка держит вес 0. Ставим на нее четвертую посылку — первая держит вес w4 = 2.
  • T = 4: Приходит пятая посылка. Поставить ее на верхнюю на платформе мы не можем, так как первая посылка, в таком случае, будет держать вес w4 + w5 = 3, что выше ее прочности s1 = 2, что недопустимо. Пропускаем пятую посылку, не получая за нее ничего.
  • T = 5: Ничего не происходит.
  • T = 6: Выдаем сначала четвертую, потом первую посылку, получая за них v1 + v4 = 3 бурля.

Заметим, что можно было пропустить четвертую посылку и поставить пятую вместо нее, однако в этом случае полученная сумма составила бы 4 бурля.