Совсем недавно Петя сдал выпускные экзамены и уже спланировал свою будущую карьеру IT-специалиста. Самое первое, что ему предстоит сделать по плану - за следующие два года устроиться в какую-нибудь IT-компанию, а для этого нужно пройти собеседования.

Петя нашел N компаний. Для i-й компании он узнал номер месяца m_i (месяцы нумеруются с нуля), когда в ней будут проводиться собеседованию на интересующую Петю должность, величину заработной платы p_i и необходимый навык прохождения собеседований c_i. На собеседование в каждую компанию можно прийти в любой день, указанного месяца, в любое время, но только один раз. Можно считать, что длительность собеседования достаточно мала, чтобы Петя мог посетить их все.

Изначально Петя обладает навыком прохождения собеседования S = 0. После посещения (успешного или нет) любого собеседования его навык увеличивается на K единиц.

Петя может успешно пройти собеседование в i-й компании, только если c_i ≤ S. После успешного прохождения собеседования, Петя может начать работать с зарплатой p_i со следующего месяца, либо отказаться. В первом случае он больше не будет проходить никаких других собеседований. Даже если у Пети не достаточно опыта для того, чтобы пройти собеседование, он все равно может получить за него опыт.

Петя хочет заработать как можно больше за следующие два года. Помогите ему оптимально распланировать график посещения собеседований.