II Razılaşması
Dünyanın hər yerindən inəklər konfransa gəliblər.
Kiçik bir çəmənlikdə çox nadir bir ot bitir. Buna görə də konfransa gələn bütün n inək bu otu dadmaq istəyir. Onlar böyük bir növbədə düzülürlər, çünki eyni anda çəmənlikdə yalnız bir inək ola bilər.
Fermer Con inək i-nin bu otlağa gəlməyi planlaşdırdığı vaxtı a[i], həmçinin bu xüsusi otlaqda keçirməyi planlaşdırdığı vaxtı t[i] bilir. Inək i ot yeməyə başladıqdan sonra, o, t[i] müddətində otlayır və bu müddət ərzində gələn bütün inəklər gözləmək məcburiyyətindədir. Əgər bir neçə inək otlağın boşalmasını gözləyirsə, daha yüksək rütbəli inək növbəti otlayan olacaq. Bu məqsədlə, bir inək başqa bir inək ot yeməyi bitirdikdə dərhal gəlirsə, o "gözləyən" adlanır. Eyni zamanda bir neçə inək gəlirsə və heç bir inək otlamırsa, daha yüksək rütbəli inək ot yeməyə başlayır.
Fermer Con-a hər hansı bir inəyin gözləməli olduğu maksimum vaxtı (vaxt a[i] ilə ot yeməyə başladığı vaxt arasındakı fərq) hesablamasına kömək edin.
Giriş Məlumatları
Girişin ilk sətrində n (1 ≤ n ≤ 10^5) verilir. Sonrakı n sətirdən hər biri n inəyin təfərrüatlarını rütbə sırasına görə göstərir (daha yüksək rütbəli inək birinci). Hər sətir bir inək üçün a[i] və t[i] dəyərlərini ehtiva edir. t[i] - müsbət tam ədədlərdir və 10^4-dən çox deyil, a[i] - müsbət tam ədədlərdir və 10^9-dan çox deyil.
Çıxış Məlumatları
Bütün inəklər arasında ən böyük potensial gözləmə vaxtını çıxış edin.
Nümunə
Bu nümunədə 5 inək var (giriş sırasına görə 1-dən 5-ə qədər nömrələnmişdir). 4 nömrəli inək ilk gələcək (vaxt 10), və o otlamanı bitirməzdən əvvəl 1 və 3 nömrəli inəklər gələcək. Çünki 1 nömrəli inək daha yüksək rütbəlidir, o, növbəti otlayan olacaq və 2 vahid vaxt gözləyəcək. O, vaxt 30-da bitirəcək və sonra 3 nömrəli inək otlamağa başlayacaq, otlamağa başlamazdan əvvəl 10 vahid vaxt gözləyəcək. Sonra heç kimin otlamadığı bir dövr olacaq. Sonra 5 nömrəli inək gələcək və o otlayarkən 2 nömrəli inək gələcək və 5 vahid vaxtdan sonra otlamağa başlayacaq. Ən çox gözləyən inək 3 nömrəli inəkdir və o, 10 vahid vaxt gözləmişdir.