Convention II#10397
Nonostante lunghi ritardi nei prelievi all'aeroporto, la convention organizzata da Farmer John per le mucche interessate a mangiare erba sta procedendo bene finora. Ha attirato mucche da tutto il mondo.
L'evento principale della convention, tuttavia, sembra che possa causare a Farmer John ulteriori grattacapi organizzativi. Un piccolissimo pascolo nella sua fattoria presenta un raro tipo di erba che, secondo le mucche più esigenti, è la più gustosa del mondo. Di conseguenza, tutte le mucche presenti alla convention vogliono assaggiare questa erba. Questo porterà probabilmente a lunghe code, dato che il pascolo è così piccolo da poter ospitare una sola mucca alla volta.
Farmer John conosce il tempo a_i in cui ciascuna mucca prevede di arrivare al pascolo speciale, così come la quantità di tempo t_i che intende trascorrere ad assaggiare l'erba una volta arrivato il suo turno. Una volta che la mucca inizia a mangiare, rimane per l'intera durata di t_i unità di tempo prima di andarsene, e durante questo periodo le altre mucche che arrivano devono aspettare. Se diverse mucche sono in attesa quando il pascolo si libera di nuovo, la mucca con l'anzianità più alta ha il permesso di assaggiare l'erba successivamente. A tale scopo, una mucca che arriva esattamente nel momento in cui un'altra mucca finisce di mangiare è considerata in attesa. Allo stesso modo, se diverse mucche arrivano esattamente nello stesso momento mentre nessuna mucca sta mangiando, quella con l'anzianità più alta mangia successivamente.
Aiuta FJ a calcolare il tempo massimo di attesa in coda per qualsiasi mucca (tra il suo tempo di arrivo a_i e il momento in cui inizia a mangiare).
La prima riga contiene un intero n~(1 \le n \le 10^5). Ciascuna delle successive righe descrive una mucca e contiene due interi a_i e t_i~(1 \le a_i \le 10^9, 1 \le t_i \le 10^4). Le mucche sono elencate in ordine di anzianità, a partire dalla più anziana.
Stampa un intero — il tempo massimo di attesa su tutte le mucche.
Esempio 1
In questo esempio, ci sono mucche, numerate nell'ordine in cui compaiono nell'input. La mucca arriva per prima (al tempo ), e prima che finisca di mangiare (al tempo ), arrivano sia la mucca che la mucca . Poiché la mucca ha un'anzianità maggiore, mangia successivamente, avendo atteso unità di tempo dal suo arrivo. Finisce al tempo , e poi la mucca inizia a mangiare, avendo atteso unità di tempo dal suo arrivo. Dopo un periodo in cui nessuna mucca sta mangiando, arriva la mucca , e mentre sta mangiando arriva la mucca ; la mucca inizia a mangiare unità di tempo dopo il suo arrivo. Quindi, la mucca che attende più a lungo è la mucca .