|
«Стабильный» интернет
(Время: 1 сек. Память: 16 Мб Сложность: 55%)
Закончив университет, Петя решил заняться разработкой web-приложений. Получив первый заказ, Петя посчитал разумным на время выполнения заказа обеспечить себя доступом в Интернет. Провайдер, с которым Петя заключил контракт, обеспечивает доступ в Интернет только посредством сервис-карт. Когда Петя пришел в местное почтовое отделение за их покупкой, то оказалось, что в продаже имеется N сервис-карт.
Каждая сервис-карта характеризуется тремя числами Bi, Ei, Si, где Si – цена карты, а Bi и Ei – это начало и окончание промежутка времени её действия, т.е. сервис-карта позволяет получить доступ в Интернет в любой момент времени t такой, что Bi ≤ t ≤ Ei. Время отсчитывается от некоторого фиксированного момента в прошлом.
Петя решил, что будет работать над выполнением заказа, начиная с момента времени B и заканчивая моментом времени E. Основная проблема состоит в том, что Петя не богат, поэтому он хочет на время выполнения заказа обеспечить себя «стабильным» Интернетом и потратить на это как можно меньшую сумму денег. Будем говорить, что данное множество сервис-карт обеспечивает Пете «стабильный» Интернет, если для любого момента времени t, такого, что B ≤ t ≤ E, найдется хотя бы одна сервис-карта из данного множества, которая позволяет получить доступ в Интернет в этот момент времени.
Ваша задача состоит в том, чтобы определить минимальную сумму денег, необходимую Пете для приобретения множества карт, которое обеспечит ему «стабильный» Интернет на время выполнения заказа.
Входные данные
В первой строке входного файла INPUT.TXT находится одно число N. Во второй строке два числа B и E, разделенные пробелом, где B – момент начала промежутка времени, в который Петя будет работать над выполнением заказа, а E – момент окончания.
Следующие N строк описывают сервис-карты, i-ая из этих строк описывает i-ю сервис-карту и содержит три числа Bi, Ei и Si, разделенные одиночными пробелами.
Ограничения: все числа натуральные, 1 ≤ N ≤ 105, 1 ≤ Bi < Ei ≤ 109, 1 ≤ B < E ≤ 109, 1 ≤ Si ≤ 20 000.
Существует хотя бы одно множество карт, которое обеспечивает «стабильный» Интернет на время выполнения заказа
Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число, равное минимальной сумме денег, необходимой Пете для приобретения множества сервис-карт, которое обеспечит ему «стабильный» Интернет на время выполнения заказа.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 7
10 30
9 14 10
13 19 18
14 18 16
18 24 14
24 30 9
17 2005 24
15 20 14 | 49 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
