Bagnine (Platino)#10426
Il contadino Giovanni ha aperto una piscina per le sue mucche, ritenendo che ciò le avrebbe aiutate a rilassarsi e a produrre più latte.
Per garantire la sicurezza, assume mucche come bagnine, ognuna delle quali lavora in un turno che copre un intervallo continuo di tempo durante la giornata. Per semplicità, supponiamo che la piscina sia aperta ogni giorno dall'istante all'istante 10^9, quindi ogni turno può essere descritto da due numeri interi: gli istanti di inizio e fine del turno della mucca. Ad esempio, una bagnina che inizia il turno all'istante t = 4 e lo termina all'istante t = 7 copre tre unità di tempo (gli estremi del turno indicano istanti di tempo).
Sfortunatamente, il contadino Giovanni ha assunto bagnine in più di quante possa permettersi di pagare. Sapendo che deve licenziare esattamente bagnine, qual è la quantità massima di tempo che i turni delle bagnine rimanenti possono ancora coprire? Un istante di tempo si considera coperto se almeno una bagnina è in servizio in quel momento.
La prima riga contiene due numeri interi e k~(1 \le k \le 100, k \le n \le 10^5). Ciascuna delle successive righe contiene due numeri interi s_i e t_i~(0 \le s_i \lt t_i \le 10^9) — gli istanti di inizio e fine del turno della -esima bagnina. Tutti gli estremi dei turni sono distinti. I turni di bagnine diverse possono sovrapporsi.
Stampare la quantità massima di tempo che può ancora essere coperta dopo che il contadino Giovanni ha licenziato bagnine.
Esempio 1
Il contadino Giovanni dovrebbe licenziare le bagnine i cui turni sono e .