Ярослав — владелец небольшой курьерской службы. Недавно он приобрел и внедрил новую систему обработки посылок. Каждая посылка представляет собой коробку, имеющую свой вес и прочность. Система устроена так, что внутри нее находится изначально пустая платформа, на которую можно ставить коробки по следующим правилам:
- Если платформа пуста, коробка ставится непосредственно на платформу, в противном случае — на самую верхнюю коробку, находящуюся на платформе.
- Суммарный вес всех коробок, находящихся на платформе, в любой момент времени не должен превышать прочности платформы S.
- Прочность любой находящейся на платформе коробки в любой момент времени должна быть не меньше суммарного веса коробок, стоящих выше.
Снимать с платформы можно только самую верхнюю коробку.
На вход системе поступают n посылок, при этом i-я посылка поступает ровно в момент времени ini, ее вес и прочность равны wi и si соответственно. Каждая посылка имеет свою стоимость vi бурлей, однако, чтобы получить эту стоимость, системе необходимо выдать посылку ровно в момент времени outi, в противном случае Ярослав получит за нее 0 бурлей. Таким образом, любую посылку можно пропустить и не ставить на платформу, формально выдав ее в момент времени ini и не получив за нее ничего.
Любая операция в задаче выполняется мгновенно. Это означает, что в один и тот же момент времени можно совершить сразу несколько операций по приему и выдаче посылок, причем в любом порядке.
Обратите внимание, что посылка, выданная в момент времени outi, сразу же оказывается вне системы, и следующие действия, происходящие в этот же момент времени, производятся без ее учета.
Поскольку система очень сложна, а поступающих посылок очень много, Ярослав просит Вас сказать, какую максимальную сумму денег он может получить с помощью своей системы.
Примечание
Пояснение ко второму примеру (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 бурля.