Становимся инфлюенсером
В последнее время вы активно публиковали контент в социальных сетях. Теперь вы хотите проанализировать период, в который ваш контент был на пике популярности. Вам нужно определить максимальное количество просмотров за период, длина которого не превышает временной интервал
t.Входные данные
В первой строке даны два целых числа
n (1 ≤ n ≤ ) — количество опубликованных материалов и t (1 ≤ t ≤ ) — максимальный временной промежуток, который вы хотите учитывать.В следующих
n строках находятся разделённые пробелами целые числа , — время публикации и количество полученных просмотров (1 ≤ , ≤ ).Выходные данные
Программа должна вывести максимальную сумму просмотров за любой период, длина которого не превышает
t.Примеры
Вход | Выход |
4 5
10 1000
12 1500
6 2000
1 1100 | 3100 |
Пояснение
Две последние публикации, сделанные в моменты времени 1 и 6, дают суммарно 2000 + 1100 просмотров.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB