Bagnine (Bronze)#10418
Il contadino John ha aperto una piscina per le sue mucche, pensando che le aiuterà a rilassarsi e a produrre più latte.
Per garantire la sicurezza, assume mucche come bagnine, ognuna delle quali ha un turno che copre un intervallo di tempo contiguo durante la giornata. Per semplicità, la piscina è aperta ogni giorno dall'istante t = 0 all'istante t = 1000, quindi ogni turno può essere descritto da due numeri interi: gli istanti in cui una mucca inizia e termina il proprio turno. Ad esempio, una bagnina che inizia all'istante t = 4 e termina all'istante t = 7 copre tre unità di tempo (si noti che gli estremi sono "punti" nel tempo).
Purtroppo, il contadino John ha assunto una bagnina in più rispetto a quante può permettersene. Dato che deve licenziare esattamente una bagnina, qual è la massima quantità di tempo che può ancora essere coperta dai turni delle bagnine rimanenti? Un intervallo di tempo è coperto se è presente almeno una bagnina.
La prima riga contiene un numero intero (1 \le n \le 100). Ognuna delle successive righe descrive una bagnina mediante due numeri interi compresi tra e : gli istanti di inizio e di fine del turno di quella bagnina. Tutti questi estremi sono distinti. I turni di bagnine diverse possono sovrapporsi.
Stampare un numero intero: la massima quantità di tempo che può ancora essere coperta se il contadino John licenzia una bagnina.
Esempio 1