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

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

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

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

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

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

В первой строке содержится целое число $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$, если скосить всю траву на газоне невозможно. Иначе, нужно вывести одно число --- количество роботов, у которых нужно изменить направление на противоположное, чтобы газон был скошен.

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