Ինֆլուենսեր դառնալը
Վերջին մի քանի ամիսներին դուք բազմիցս տարբեր բովանդակություն եք հրապարակել սոցիալական մեդիայում: Հիմա ցանկանում եք հայտնաբերել այն ամենահաջող շրջանը, որի ընթացքում ձեր գրառումները հավաքել են առավելագույն դիտումներ: Այսինքն՝ ձեզ հետաքրքրում է, թե առավելագույն ինչ դիտումների գումար կարող եք ստանալ այնպիսի ժամանակահատվածում, որի տևողությունը չի գերազանցում
t-ը:Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր
n (1 ≤ n ≤ 10^5) — հրապարակումների քանակը և t (1 ≤ t ≤ 10^9) — այն ժամանակային առավելագույն տևողությունը, որը նկատի եք առնում:Հաջորդ
n տողերից յուրաքանչյուրում տրված են երկու ամբողջ թվեր t_i և v_i, որոնք բաժանված են բացատով: t_i-ն ցույց է տալիս հրապարակման պահը, իսկ v_i-ն՝ տվյալ հրապարակման դիտումների քանակը (1 ≤ t_i, v_i ≤ 10^9):Ելք
Ծրագիրը պետք է տպի դիտումների առավելագույն գումարը, որը տեղավորվում է
t-ից չգերազանցող ժամանակահատվածում:Օրինակներ
Մուտք | Ելք |
4 5
10 1000
12 1500
6 2000
1 1100 | 3100 |
Բացատրություն
Վերջին երկու հրապարակումները (1 և 6 ժամանակային պահերին) ունեն 1100 և 2000 դիտումներ, համապատասխանաբար: Այդ գրառումների ընդհանուր դիտումների գումարը 3100 է:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB