تُجزّ المروج في Иннополис بواسطة روبوتات كهربائية لجزّ العشب. سنعتبر أن المرج قطعة من خط الأعداد، تقع روبوتات جزّ العشب عند بعض نقاطها. يمكن إهمال أحجام الروبوتات. يقف أحد الروبوتات عند بداية المرج (لا يوجد مرج إلى يساره)، ويقف آخر عند نهايته (لا يوجد مرج إلى يمينه). يتجه كل روبوت في البداية في أحد اتجاهين: إلى اليمين أو إلى اليسار.

تكفي شحنة الروبوت رقم $i$ لجزّ $p_i$ مترًا من المرج. بعد الشحن الليلي، تبدأ جميع الروبوتات العمل في الوقت نفسه وتتحرك بالسرعة نفسها. يتحرك كل روبوت على امتداد الخط في اتجاهه. يتوقف الروبوت في إحدى الحالات الثلاث الآتية:

1. إذا نفدت شحنته. بعبارة أخرى، إذا قطع الروبوت رقم $i$ مسافة $p_i$ مترًا من نقطة انطلاقه.
2. إذا وصل الروبوت إلى بداية المرج أو نهايته.
3. إذا التقى الروبوت عند نقطة واحدة بروبوت آخر كان يتحرك نحوه أو توقف عند تلك النقطة سابقًا.

قبل تشغيل الروبوتات، يمكنك عكس اتجاه بعض منها. يجب جزّ العشب في المرج كله.

حدد أقل عدد من الروبوتات التي يجب عكس اتجاهها حتى يُجزّ في النهاية كل العشب في المرج. وإلا، فأبلغ بأن جزّ كل العشب مستحيل.

الإدخال

يحتوي السطر الأول على عدد صحيح $n$ ($2\le n\le10^5$)، وهو عدد الروبوتات.

تحتوي الأسطر الـ $n$ التالية على أوصاف الروبوتات بترتيب مواقعها على الخط من اليسار إلى اليمين. يوصف كل روبوت بثلاثة أعداد صحيحة $x_i,p_i,d_i$: موقعه الابتدائي، وعدد الأمتار التي يمكنه قطعها، واتجاه حركته ($0=x_1<x_2<\ldots<x_n\le10^9$، $1\le p_i\le10^9$؛ تشير القيمة $d_i=-1$ إلى الحركة يسارًا، في اتجاه تناقص الإحداثي، وتشير القيمة $d_i=1$ إلى الحركة يمينًا، في اتجاه تزايد الإحداثي). تقع بداية المرج ونهايته عند النقطتين $x_1=0$ و$x_n$، على الترتيب.

الإخراج

اطبع $-1$ في سطر واحد إذا كان جزّ كل العشب في المرج مستحيلًا. وإلا، فاطبع عددًا واحدًا: عدد الروبوتات التي يجب عكس اتجاهها حتى يُجزّ المرج.

المهام الفرعية

أمثلة

الإدخال 1

3
0 1 -1
1 1 1
2 1 -1

الإخراج 1

1

الإدخال 2

2
0 1 1
4 2 -1

الإخراج 2

-1

ملاحظة

يوضح الشكل المثال الأول. لجزّ كل العشب، يمكن، مثلًا، عكس اتجاه الروبوت الذي يقف في المنتصف.