Шахтёр Василий заинтересовался криптовалютой SillyCoin. Майнеры этой валюты получают расписание блоков на следующие сутки. Для каждого блока известен промежуток времени, в течение которого его потребуется майнить, и вознаграждение в монетках SillyCoin, которое гарантированно выдаётся, если этот блок непрерывно майнился в указанное время. Майнер решает сам, стоит ли браться за майнинг того или иного блока. Майнинг следующего блока можно начинать в ту же секунду, как закончена обработка предыдущего блока. У Василия всего одного видеокарта, поэтому он не может майнить несколько блоков одновременно. Кроме того, Василию регулярно приходят счета за электричество, которое придётся оплачивать за фактически потраченное на майнинг время по фиксированному тарифу. Василий хочет узнать, выгодно ли ему заниматься майнингом, поэтому он просит вас написать программу, вычисляющую по заданному расписанию блоков максимально возможную выгоду.
В первой строке находятся два целых числа N и C (1 ≤ N < 86 400, 0 ≤ C ≤ 1000), разделённых пробелом, — количество блоков в расписании и стоимость электричества, затрачиваемого за каждую секунду майнинга, в монетках. В следующих N строках содержится расписание блоков на следующие сутки.
В каждой строке через пробел указаны время начала и окончания блока (в формате HH:MM:SS от 00:00:00 до 23:59:59 с разницей минимум в 1 секунду) и вознаграждение P (0 ≤ P ≤ 105) в монетках.
Вывести целое число — максимальное вознаграждение, которое Василий может получить за майнинг. Если майнинг принесёт лишь убытки, следует вывести 0.
4 0
03:00:00 10:10:00 20
01:00:00 02:30:00 50
16:10:00 19:00:00 100
02:30:00 22:00:00 200
250
3 1
16:59:00 17:00:00 100
01:01:01 01:01:11 20
12:00:00 13:00:00 3601
51
4 10
00:00:05 00:01:55 1100
00:00:10 00:00:21 100
00:01:50 00:02:00 80
23:59:00 23:59:05 40
0
