Восстание газонокосилок

시간 제한1초메모리 제한2048 MB

요약

선분 위 로봇들의 방향을 정해 모든 잔디를 깎으면서 방향을 바꾸는 로봇 수를 최소로 줄이는 문제.

난이도: 어려움10점 중 8점
유형: 그리디, 정렬, 구현, 구간
정답자: 아직 제출이 없습니다

문제

Газоны в Иннополисе косят электрические роботы-газонокосилки. Будем считать, что газон представляет собой отрезок числовой прямой, на котором в некоторых точках расположены роботы-газонокосилки. Размером роботов можно пренебречь. Один из роботов стоит в начале газона (левее него газона нет), и один --- в конце (правее него газона нет). Каждый робот изначально ориентирован в одном из двух направлений: либо направо, либо налево.

Заряда $i$ -го робота хватает для обработки $p\_i$ метров газона. После ночной зарядки все роботы начинают работать одновременно и движутся с одинаковой скоростью. Каждый робот движется в своём направлении вдоль прямой. Робот останавливается в одном из трёх случаев:

Если у робота закончился заряд. Иными словами, если $i$ -й робот проехал $p\_i$ метров от точки старта.
Если робот доехал до начала или конца газона.
Если робот встретился в одной точке с другим роботом, который двигался ему навстречу или остановился в этой точке ранее.

Перед запуском роботов вы можете поменять направление некоторых из них на противоположное. Требуется скосить траву на всём газоне.

Определите, у какого минимального количества роботов нужно поменять направление, чтобы в итоге вся трава на газоне оказалась скошена. Иначе сообщите, что всю траву скосить невозможно.

입력

В первой строке содержится целое число $n$ ( $2 \leq n \leq 10^5$ ) --- количество роботов.

В следующих $n$ строках содержатся описания роботов в порядке их расположения на прямой слева направо. Каждый робот характеризуется тремя целыми числами $x\_i$ , $p\_i$ , $d\_i$ : начальной позицией робота, количеством метров, которые он может проехать, и направлением движения ( $0 = x\_1 < x\_2 < \ldots < x\_n \le 10^9$ , $1 \le p\_i \le 10^9$ , значение $d\_i = -1$ обозначает движение налево, в направлении уменьшения координаты, $d\_i = 1$ обозначает движение направо, в направлении увеличения координаты). Начало и конец газона находятся в точках $x\_1=0$ и $x\_n$ соответственно.

출력

В единственной строке необходимо вывести $-1$ , если скосить всю траву на газоне невозможно. Иначе, нужно вывести одно число --- количество роботов, у которых нужно изменить направление на противоположное, чтобы газон был скошен.

힌트

Первый пример изображен на рисунке. Для того, чтобы скосить всю траву, можно, например, развернуть робота, который стоит посередине.

예제2

예제 1
입력
```
3
0 1 -1
1 1 1
2 1 -1
```
예상 출력
```
1
```
예제 2
입력
```
2
0 1 1
4 2 -1
```
예상 출력
```
-1
```