La Lista dei Secchi#10394
Farmer John sta considerando un cambiamento nel modo in cui assegna i secchi per mungere le sue mucche. Pensa che questo gli permetterà alla fine di usare meno secchi in totale, ma non è sicuro di quanti ne avrà effettivamente bisogno. Aiutatelo!
Farmer John ha mucche, comodamente numerate . La -esima mucca deve essere munta dal tempo s_i al tempo t_i e richiede b_i secchi durante il processo di mungitura. Più mucche possono essere munte nello stesso momento; in tal caso, non possono condividere i secchi. Cioè, un secchio assegnato alla mucca non può essere usato per mungere nessun'altra mucca tra il tempo s_i e il tempo t_i. Ovviamente, il secchio può essere usato per altre mucche al di fuori di questo intervallo di tempo. Per semplificare il suo lavoro, FJ si è assicurato che in ogni istante, la mungitura di al massimo una mucca inizia o finisce (cioè, tutti i valori s_i e t_i sono distinti).
FJ ha un magazzino contenente secchi numerati in sequenza con le etichette , , , e così via. Secondo la sua nuova strategia di mungitura, ogni volta che una mucca inizia ad essere munta (al tempo s_i), FJ corre al magazzino, prende i b_i secchi disponibili con le etichette più piccole, e li assegna alla mucca .
Determinate il numero totale di secchi che FJ deve tenere nel suo magazzino per riuscire a mungere tutte le mucche.
La prima riga contiene un intero n~(1 \le n \le 100). Ciascuna delle successive righe descrive una mucca e contiene tre interi s_i, t_i, e b_i~(1 \le s_i, t_i \le 1000, 1 \le b_i \le 10).
Stampate un intero — il numero totale di secchi di cui FJ ha bisogno.
In questo esempio, FJ ha bisogno di secchi. Usa i secchi e per mungere la mucca (che inizia al tempo ) e il secchio per mungere la mucca (che inizia al tempo ). Quando la mucca arriva al tempo , i secchi e sono di nuovo disponibili, ma il secchio non lo è, quindi usa i secchi , , e .
Esempio 1