Misurazione del latte (Argento)#10513

Misurazione del latte (Argento)

1 secondo
128 megabyte
Difficile

Inizialmente, ogni mucca del contadino John produce galloni di latte al giorno. Poiché la produzione di latte di una mucca può cambiare nel tempo, il contadino John decide di misurare periodicamente la quantità di latte prodotta e di registrare i risultati in un registro. Le voci nel suo registro sono simili a queste:

35 1234 -2
14 2345 +3

La prima voce indica che al giorno la produzione di latte della mucca era di galloni inferiore rispetto alla misurazione precedente. La voce successiva indica che al giorno la produzione di latte della mucca è aumentata di galloni rispetto alla misurazione precedente. Il contadino John riesce a effettuare al massimo una misurazione in un dato giorno. Sfortunatamente, è un po' disorganizzato e registra i risultati delle misurazioni non necessariamente in ordine cronologico.

Per mantenere motivate le sue mucche, il contadino John appende con orgoglio sul muro della sua stalla le fotografie di tutte le mucche che al momento hanno la produzione di latte più alta. Se più mucche hanno la stessa produzione massima, appende le fotografie di tutte queste mucche. Determinate il numero di giorni in cui il contadino John avrebbe dovuto modificare questa esposizione.

Notate che il contadino John possiede una mandria di mucche molto numerosa. Pertanto, sebbene nel suo registro possano essere annotate le mucche che hanno cambiato la propria produzione di latte, esistono sempre abbastanza altre mucche la cui produzione rimane pari a galloni.

Input

La prima riga contiene il numero di misurazioni n~(1 \le n \le 10^5) effettuate dal contadino John, nonché il numero g~(1 \le g \le 10^9). Ciascuna delle successive righe contiene una misurazione nel formato descritto sopra: il giorno (un intero nell'intervallo 1 \ldots 10^6), l'ID intero della mucca (nell'intervallo 1 \ldots 10^9) e la variazione della sua produzione di latte rispetto alla misurazione precedente (un intero non nullo). La produzione di latte di ogni mucca rimarrà sempre nell'intervallo 0 \ldots 10^9.

Output

Stampate il numero di giorni in cui il contadino John ha avuto la necessità di modificare la sua esposizione motivazionale.

Esempi

Esempio 1

Loading
Loading