את המדשאות ב־Иннополис מכסחים רובוטים חשמליים לכיסוח דשא. נניח שהמדשאה היא קטע על ישר המספרים, ושבכמה נקודות עליו נמצאים רובוטים לכיסוח דשא. אפשר להזניח את גודל הרובוטים. אחד הרובוטים עומד בתחילת המדשאה (אין מדשאה משמאלו), ואחד בקצה המדשאה (אין מדשאה מימינו). כל רובוט פונה בתחילה לאחד משני הכיוונים: ימינה או שמאלה.

הטעינה של הרובוט ה־$i$ מספיקה לכיסוח $p_i$ מטרים של מדשאה. לאחר טעינה במהלך הלילה, כל הרובוטים מתחילים לעבוד בו־זמנית ונעים באותה מהירות. כל רובוט נע בכיוון שלו לאורך הישר. רובוט נעצר באחד משלושת המקרים הבאים:

1. אם אזלה הטעינה שלו. במילים אחרות, אם הרובוט ה־$i$ עבר $p_i$ מטרים מנקודת ההתחלה.
2. אם הרובוט הגיע לתחילת המדשאה או לקצה שלה.
3. אם הרובוט נפגש באותה נקודה עם רובוט אחר, שנע לקראתו או שכבר נעצר בנקודה הזאת קודם לכן.

לפני הפעלת הרובוטים, תוכלו להפוך את כיוון התנועה של חלק מהם. יש לכסח את הדשא בכל המדשאה.

מצאו את המספר המינימלי של רובוטים שיש להפוך את כיוון התנועה שלהם כך שבסופו של דבר כל הדשא במדשאה יהיה מכוסח. אם הדבר אינו אפשרי, הודיעו שאי אפשר לכסח את כל הדשא.

קלט

השורה הראשונה מכילה מספר שלם $n$ ($2 \le n \le 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$ אם אי אפשר לכסח את כל הדשא במדשאה. אחרת, יש להדפיס מספר אחד — מספר הרובוטים שיש להפוך את כיוונם כדי שהמדשאה תהיה מכוסחת.

תתי־משימות

דוגמאות

קלט 1

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

פלט 1

1

קלט 2

2
0 1 1
4 2 -1

פלט 2

-1

הסבר

הדוגמה הראשונה מוצגת באיור. כדי לכסח את כל הדשא אפשר, למשל, להפוך את כיוון הרובוט שנמצא באמצע.