Дом интернета — одна из самых больших и наиболее хорошо оборудованных аудиторий университета. Кроме турниров по программированию, в Доме интернета проводится множество других мероприятий — семинары, конференции, киберспортивные чемпионаты и так далее.
Чтобы распределить время пользования аудиторией между всеми желающими, в начале учебного года администраторы Дома интернета изучают заявки на проведение мероприятий и формируют календарный план. Это достаточно непростая работа, поэтому, как всегда, Макса попросили помочь её автоматизировать.
В этом году поступило N заявок на проведение мероприятий. Мероприятие под номером i будет занимать Дом интернета в интервале времени [T1i; T2i]. Два мероприятия не могут проходить одновременно, но в тот момент, когда одно из мероприятий завершается, может сразу начаться другое.
Важность i-го мероприятия оценивается величиной Bi. Макс хочет выбрать мероприятия таким образом, чтобы они не пересекались, а их суммарная важность оказалась как можно больше. Помогите ему составить оптимальный план мероприятий.