Cütlükdə (Qızıl)#11225
n inək ədədi oxda yerləşdirilib. i-ci inəyin yeri x[i] ədədi ilə, çəkisi isə y[i] ədədi ilə verilib.
Fermer Conun siqnalı ilə bəzi inəklər cütlər təşkil edir ki,
Hər bir cüt iki fərqli inəkdən a və b ibarətdir, onların yerləri bir-birindən k-dən çox uzaq deyil, yəni |x[a] − x[b]| ≤ k.
Hər bir inək ya hansısa cütün bir hissəsidir, ya da heç bir cütün bir hissəsi deyil.
Cütləşmə maksimal adlanır, əgər cütləşməmiş inəklərdən heç biri cüt təşkil edə bilmirsə.
Cütləşməmiş inəklərin çəkilərinin mümkün cəmi intervalını müəyyən edin. Yəni
Əgər t = 1, cütləşməmiş inəklərin çəkilərinin minimal mümkün cəmini hesablayın.
Əgər t = 2, cütləşməmiş inəklərin çəkilərinin maksimal mümkün cəmini hesablayın.
Girişin birinci sətiri t, n (1 ≤ n ≤ 10^5), k (1 ≤ k ≤ 10^9) ədədlərini ehtiva edir.
Sonrakı n sətirdən hər biri i-ci sətir x[i] (0 ≤ x[i] ≤ 10^9) və y[i] (1 ≤ y[i] ≤ 10^4) ədədlərini ehtiva edir. 0 ≤ x[1] < x[2] < ... < x[n] ≤ 10^9 təmin edilir.
Cütləşməmiş inəklərin çəkilərinin minimal və ya maksimal mümkün cəmini çıxarın.
Bu nümunədə inəklər 2 və 4 cütləşə bilər, çünki onların arasındakı məsafə 2-yə bərabərdir. Bu optimaldır, çünki digər cütləşmələr ümumiyyətlə mümkün deyil: İnəklər 1 və 3 arasındakı məsafə 3-dür. İnəklər 3 və 5 arasındakı məsafə 3-dür. İnəklər 1 və 5 arasındakı məsafə 6-dır. Cütləşməmiş inəklərin çəkilərinin cəmi: 2 + 2 + 2 = 6.
Burada inəklər 1 və 2 cütləşə bilər, çünki onlar 2 məsafəsindədirlər (≤ k). İnəklər 4 və 5 də cütləşə bilər, çünki onlar da 2 məsafəsindədirlər (≤ k). Son cütləşmə optimaldır, çünki yalnız inək 3 cütləşməmiş qalır, onun çəkisi 2-dir.
Bu nümunə üçün cavab 693 + 992 + 785 = 2470-dir.
Nümunə 1
Nümunə 2
Nümunə 3