Konvansiyon II#10397

Konvansiyon II

1 saniye

128 megabayt

Orta

Havaalanı karşılamalarındaki uzun gecikmelere rağmen, Çiftçi John'un ot yemekle ilgilenen inekler için düzenlediği konvansiyon şimdiye kadar iyi gidiyor. Dünyanın dört bir yanından inekleri kendine çekti.

Ancak konvansiyonun ana etkinliği, Çiftçi John'a programlama konusunda ek sıkıntılar yaratacak gibi görünüyor. Çiftliğindeki çok küçük bir mera, titiz ineklere göre dünyanın en lezzetlisi olan nadir bir ot türüne sahip. Sonuç olarak, konvansiyondaki tüm $n$ inek bu otu tatmak istiyor. Mera o kadar küçük ki aynı anda sadece bir ineğe yer verebildiğinden, bu durum muhtemelen uzun kuyruklara yol açacak.

Çiftçi John, her bir $i$ ineğinin özel meraya varmayı planladığı zamanı $a_{i}$ a_i olarak bildiği gibi, sırası geldiğinde otu tatmak için harcamayı planladığı süreyi de $t_{i}$ t_i olarak bilmektedir. $i$ ineği yemeye başladığında, ayrılmadan önce tam $t_{i}$ t_i birim zaman boyunca kalır ve bu süre boyunca diğer gelen inekler beklemek zorundadır. Mera tekrar boşaldığında birden fazla inek bekliyorsa, kıdemi en yüksek olan inek bir sonraki sırada otu tatma hakkına sahiptir. Bu amaçla, tam olarak başka bir inek yemeyi bitirdiği anda gelen bir inek, bekliyor olarak kabul edilir. Benzer şekilde, hiçbir inek yemek yemiyorken birden fazla inek tam olarak aynı anda gelirse, kıdemi en yüksek olan inek bir sonraki sırada yer.

FJ'ye, herhangi bir ineğin kuyrukta beklemek zorunda kaldığı maksimum süreyi (ineğin $a_{i}$ a_i varış zamanı ile yemeye başladığı an arasındaki süreyi) hesaplamasına yardım et.

Giriş

İlk satır bir $n (1 \leq n \leq 1 0^{5})$ n~(1 \le n \le 10^5) tamsayısını içerir. Sonraki $n$ satırın her biri bir ineği tanımlar ve $a_{i}$ a_i ile $t_{i} (1 \leq a_{i} \leq 1 0^{9}, 1 \leq t_{i} \leq 1 0^{4})$ t_i~(1 \le a_i \le 10^9, 1 \le t_i \le 10^4) olmak üzere iki tamsayı içerir. İnekler, en kıdemlisinden başlayarak kıdem sırasına göre listelenmiştir.

Çıktı

Tüm inekler arasındaki maksimum bekleme süresini ifade eden tek bir tamsayı yazdırın.

Örnekler

Örnek 1

Not

Bu örnekte, girdide göründükleri sıraya göre $1 \dots 5$ olarak numaralandırılmış $5$ inek vardır. İnek $4$ ilk önce gelir (zaman $10$ 'da) ve o yemeyi bitirmeden önce (zaman $27$ 'de), hem $1$ hem de $3$ inekleri gelir. İnek $1$ daha yüksek kıdeme sahip olduğundan, bir sonraki sırada o yer ve varışından itibaren $2$ birim zaman beklemiş olur. Zaman $30$ 'da yemeyi bitirir ve ardından inek $3$ yemeye başlar; bu inek, varışından itibaren $10$ birim zaman beklemiştir. Hiçbir ineğin yemek yemediği bir sürenin ardından, inek $5$ gelir ve o yemek yerken inek $2$ gelir; inek $2$ , varışından $5$ birim zaman sonra yemeye başlar. Böylece, en uzun süre bekleyen inek, inek $3$ 'tür.