우유 측정

시간 제한2초메모리 제한512 MB

요약

측정값을 날짜순으로 정렬한 뒤, 각 갱신을 적용한 직후 최대 우유 생산량을 가진 소들의 집합이 바뀌는 날의 수를 센다.

난이도: 보통10점 중 6점
유형: 정렬, 해시맵, 구현, 그리디
정답자: 아직 제출이 없습니다

문제

존 농부의 소는 처음에 모두 하루에 $G$ 갤런의 우유를 생산한다 ( $1 \le G \le 10^9$ ). 생산량은 시간이 지나면서 달라지기도 해서, 존 농부는 이따금 생산량을 재어 기록장에 적는다. 기록은 다음과 같은 모양이다.

35 1234 -2
14 2345 +3

첫 줄은 35일에 1234번 소의 생산량이 직전 측정 때보다 2갤런 줄었다는 뜻이고, 둘째 줄은 14일에 2345번 소의 생산량이 직전 측정 때보다 3갤런 늘었다는 뜻이다. 존 농부는 하루에 많아야 한 번 측정하고, 정리에 서툴러서 기록을 날짜 순서대로 적지 않는다.

소에게 동기를 주려고 존 농부는 생산량이 가장 많은 소의 사진을 헛간 벽에 건다. 생산량이 가장 많은 소가 여럿이면 그 소의 사진을 모두 건다. 농장의 소가 워낙 많아서 기록장에 나오지 않고 생산량이 그대로 $G$ 갤런인 소가 항상 남아 있고, 최고 생산량이 $G$ 갤런이면 이런 소의 사진도 벽에 걸린다.

벽에 걸린 사진의 집합이 바뀌는 날이 며칠인지 세어라. 첫 측정 직전에는 모든 소가 $G$ 갤런을 생산하므로 모든 소의 사진이 벽에 걸려 있다. 측정이 있는 날에는 측정 직후에 생산량이 최대인 소의 집합을 측정 직전의 집합과 견주어, 두 집합이 다르면 그날을 센다.

입력

첫째 줄에 측정 횟수 $N$ ( $1 \le N \le 100000$ )과 처음 생산량 $G$ ( $1 \le G \le 10^9$ )가 주어진다. 다음 $N$ 개 줄에 측정이 한 줄에 하나씩 주어진다. 각 줄은 날짜 ( $1$ 이상 $10^6$ 이하의 정수), 소의 번호 ( $1$ 이상 $10^9$ 이하의 정수), 직전 측정 이후의 생산량 변화량으로 이루어진다. 변화량은 0이 아닌 정수이고 부호 + 또는 -를 붙여 적는다. 같은 날에 측정이 두 번 이루어지는 일은 없고, 어느 시점에서도 각 소의 생산량은 $0$ 이상 $10^9$ 이하이다.

출력

존 농부가 벽의 사진을 바꿔야 하는 날의 수를 출력한다.

예제2

예제 1
입력
```
4 10
7 3 +3
4 2 -1
9 3 -1
1 1 +2
```
예상 출력
```
3
```
예제 2
입력
```
1 5
1 7 +3
```
예상 출력
```
1
```