Konvensiya II#10397
Hava limanında uzun gecikmələrə baxmayaraq, Farmer John-un ot yeməyi sevən inəklər üçün keçirdiyi konvensiya indiyə qədər yaxşı gedirdi. O, bütün dünyadan inəkləri cəlb etmişdi.
Lakin konvensiyanın əsas hadisəsi Farmer John üçün əlavə cədvəlləşdirmə problemləri yarada bilər. Onun fermasındakı çox kiçik bir otlaq, zövqlü inəklərin fikrincə, dünyanın ən dadlı növ otuna malikdir. Nəticədə, konvensiyadakı bütün inək bu otu dadmaq istəyir. Bu, çox güman ki, uzun növbələrə səbəb olacaq, çünki otlaq o qədər kiçikdir ki, eyni vaxtda yalnız bir inəyi qəbul edə bilər.
Farmer John hər bir inəyinin xüsusi otlağa gəlmək planlaşdırdığı a_i vaxtını, həmçinin növbəsi gəldikdə otu dadmağa sərf etməyi planlaşdırdığı t_i vaxtını bilir. inəyi yeməyə başladıqdan sonra, getməzdən əvvəl tam t_i vahid vaxt qalır və bu müddətdə digər gələn inəklər gözləməlidir. Otlaq yenidən boşaldıqda bir neçə inək gözləyirsə, ən yüksək staja malik inək növbəti olaraq otu dadmaq hüququ qazanır. Bu məqsədlə, başqa bir inək yeməyini bitirdiyi anda tam gələn inək gözləyən hesab olunur. Eyni şəkildə, heç bir inək yemək yemədiyi zaman bir neçə inək tam eyni vaxtda gəlirsə, ən yüksək staja malik olan növbəti yeyən olur.
FJ-yə hər hansı bir inəyin növbədə gözləməli olduğu maksimum vaxtı hesablamağa kömək edin (onun a_i gəliş vaxtı ilə yeməyə başladığı an arasında).
Birinci sətirdə n~(1 \le n \le 10^5) tam ədədi verilir. Növbəti sətirdən hər biri bir inəyi təsvir edir və iki tam ədəd olan a_i və t_i~(1 \le a_i \le 10^9, 1 \le t_i \le 10^4) ədədlərindən ibarətdir. İnəklər stajlarına görə, ən yüksək stajlı olanından başlayaraq sadalanıb.
Bütün inəklər üzrə maksimum gözləmə vaxtını bildirən bir tam ədəd çap edin.
Nümunə 1
Bu nümunədə inək var, onlar daxiletmədə göründükləri sıraya görə nömrələnib. Cow birinci gəlir (vaxt -da), və o yeməyini bitirməzdən əvvəl (vaxt -də), həm , həm də inəkləri gəlir. inəyinin stajı daha yüksək olduğundan, o növbəti olaraq yeyir və gəlişindən bəri vahid vaxt gözləmiş olur. O, vaxt -da bitirir və sonra inəyi yeməyə başlayır, o isə gəlişindən bəri vahid vaxt gözləmiş olur. Heç bir inəyin yemək yemədiyi bir müddətdən sonra, inəyi gəlir, və o yemək yeyərkən inəyi gəlir; inəyi gəlişindən vahid vaxt sonra yeməyə başlayır. Beləliklə, ən uzun gözləyən inək inəyidir.