Bagnini (Argento)#10420
Farmer John ha aperto una piscina per le sue mucche, sperando che questo le aiutasse a rilassarsi e a produrre più latte.
Per garantire la sicurezza, assume mucche come bagnini, ognuna delle quali ha un turno che copre un intervallo continuo di tempo durante la giornata. Per semplicità, supponiamo che la piscina sia aperta ogni giorno dall'istante t = 0 all'istante t = 10^9, quindi ogni turno può essere descritto da due numeri interi: gli istanti di tempo in cui la mucca inizia e termina il proprio turno. Ad esempio, un bagnino che inizia a lavorare all'istante t = 4 e termina all'istante t = 7 copre tre unità di tempo (si noti che gli estremi dell'intervallo sono "punti" nel tempo).
Purtroppo, Farmer John ha assunto un bagnino in più di quanti possa permettersi. Sapendo che deve licenziare esattamente un bagnino, qual è la quantità massima di tempo che può essere coperta dai turni dei bagnini rimanenti? Un intervallo di tempo si considera coperto se è di turno almeno un bagnino.
La prima riga contiene un numero intero n~(1 \le n \le 10^5). Ciascuna delle successive righe descrive un bagnino con due numeri interi nell'intervallo da a 10^9: gli istanti di inizio e fine del turno di tale bagnino. Tutti questi istanti di tempo sono distinti. I turni di bagnini diversi possono sovrapporsi.
Stampa un singolo numero intero: la quantità massima di tempo che può essere coperta se Farmer John licenzia un bagnino.
Esempio 1