Ein Influencer werden
Du hast in den letzten Monaten viele Inhalte in sozialen Netzwerken veröffentlicht. Jetzt möchtest du herausfinden, in welchem Zeitraum deine Beiträge am beliebtesten waren. Dazu willst du wissen, wie viele Aufrufe deine Inhalte innerhalb eines Zeitabschnitts von höchstens
t insgesamt verzeichnet haben.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n (1 ≤ n ≤ ) – die Anzahl veröffentlichter Inhalte – und t (1 ≤ t ≤ ) – die maximale Länge des Zeitintervalls, das du betrachten möchtest.Die nächsten
n Zeilen enthalten je zwei durch Leerzeichen getrennte ganze Zahlen , wobei den Veröffentlichungszeitpunkt und die Anzahl der Aufrufe für den jeweiligen Beitrag angibt (1 ≤ ≤ ).Ausgabe
Das Programm soll die maximale Summe aller Aufrufe ausgeben, die in einem zusammenhängenden Zeitraum von höchstens
t erzielt werden können.Beispiele
Eingabe | Ausgabe |
4 5
10 1000
12 1500
6 2000
1 1100 | 3100 |
Erläuterung
Die letzten beiden Beiträge – veröffentlicht zu den Zeitpunkten 1 und 6 – würden zusammen 2000 + 1100 Aufrufe ergeben.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB