In coppia#10524
Il Contadino John ha scoperto che è più facile mungere le sue mucche quando accanto a loro si trova un'altra mucca che offre supporto morale. Per questo motivo vuole prendere le sue mucche (m \le 10^9, è un numero pari) e dividerle in coppie. Successivamente ogni coppia di mucche verrà condotta in una stalla separata del fienile per la mungitura. La mungitura in tutte le stalle avverrà simultaneamente.
Per complicare un po' le cose, ogni mucca del Contadino John produce una quantità diversa di latte. Se in una coppia vengono unite mucche con una produzione di latte pari a e , per mungerle entrambe saranno necessarie a + b unità di tempo.
Aiuta il Contadino John a determinare il tempo minimo possibile necessario per mungere tutte le sue mucche, se vengono divise in coppie nel modo ottimale.
La prima riga contiene n~(1 \le n \le 10^5). Ognuna delle successive righe contiene due numeri interi e , che indicano che il Contadino John ha mucche, ciascuna delle quali produce y~(1 \le y \le 10^9) unità di latte. La somma di tutti gli è uguale a , il numero totale di mucche. Si garantisce che sia un numero pari.
Stampa il tempo minimo necessario per mungere tutte le mucche del Contadino John, se vengono divise in coppie nel modo ottimale.
Supponiamo, ad esempio, che le mucche con una produzione di latte di e siano unite in una coppia, e le due mucche con una produzione di in un'altra. Allora la mungitura in ciascuna delle due stalle richiederà unità di tempo. Poiché la mungitura in tutte le stalle avviene simultaneamente, l'intero processo si concluderà dopo unità di tempo.
Qualsiasi altra suddivisione in coppie sarebbe non ottimale, poiché in tal caso la mungitura in almeno una stalla richiederebbe più di unità di tempo.
Esempio 1