Devenir un influenceur
Vous avez publié beaucoup de contenus sur les réseaux sociaux au cours des derniers mois. Vous souhaitez maintenant analyser la période au cours de laquelle vos publications ont obtenu le plus de popularité. Autrement dit, vous voulez déterminer le nombre maximal de vues que vos contenus ont généré pendant un intervalle de temps n’excédant pas la valeur de
t.Entrée
La première ligne de l’entrée contient deux entiers
n (1 ≤ n ≤ 10^5) — le nombre de publications — et t (1 ≤ t ≤ 10^9) — l’intervalle de temps maximal à considérer.Les
n lignes suivantes comportent chacune deux entiers séparés par un espace, t_i et v_i : l’horodatage de la publication et le nombre de vues qu’elle a obtenues (1 ≤ t_i, v_i ≤ 10^9).Sortie
Le programme doit afficher la somme maximale de vues obtenues au cours d’une période dont la durée n’excède pas
t.Exemples
Entrée | Sortie |
4 5
10 1000
12 1500
6 2000
1 1100 | 3100 |
Explication
Les deux dernières publications (à 1 et 6) totalisent 2000 + 1100 vues, ce qui donne la somme la plus élevée pour un intervalle de temps ne dépassant pas
t.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB