Tornar-se um influenciador
Nos últimos meses, tem publicado muito conteúdo nas redes sociais. Agora, pretende analisar o seu período mais popular. Gostaria de descobrir o número máximo de visualizações que o seu conteúdo obteve durante um período que não ultrapasse um intervalo de tempo de tamanho
t.Entrada
A primeira linha da entrada contém dois inteiros
n (1 ≤ n ≤ 10^5) — o número de conteúdos publicados — e t (1 ≤ t ≤ 10^9) — o intervalo máximo de tempo que deseja considerar.As próximas
n linhas contêm dois inteiros separados por espaço, t_i e v_i — o momento em que foi publicado e as visualizações obtidas na publicação (1 ≤ ti, vi ≤ 10^9).Saída
O programa deve imprimir a soma máxima de visualizações obtidas num intervalo de tempo que não exceda
t.Exemplos
Entrada | Saída |
4 5
10 1000
12 1500
6 2000
1 1100 | 3100 |
Explicação
As duas últimas publicações — feitas nos momentos 1 e 6 — resultariam em 2000 + 1100 visualizações.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB