בתחילה, Snuke אינו יכול לזוז כלל. ישנם $n$ כרטיסים, ומחירו של הכרטיס ה-$i$ הוא $p_i$. אם Snuke קונה את הכרטיס ה-$i$, אז לכל נקודה $(x, y)$ ומספר אי-שלילי $t$, הוא יכול לנוע מ-$(x, y)$ אל $(x + ta_i, y + tb_i)$. Snuke רוצה לקנות כרטיסים כך שיוכל לנוע בין כל שתי נקודות. חשבו את המחיר הכולל המינימלי האפשרי של הכרטיסים שעליו לקנות.

קלט

השורה הראשונה בקלט מכילה מספר שלם אחד $n$ ($1 \le n \le 2 \cdot 10^5$). אחריה מופיעות $n$ שורות; השורה ה-$i$ מביניהן מכילה שלושה מספרים שלמים $a_i$, $b_i$, $p_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le p_i \le 10^9$).

פלט

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

דוגמאות

קלט 1

7
0 3 1
0 3 2
1 -1 2
0 0 1
-2 4 1
-4 0 1
2 1 2

פלט 1

4

קלט 2

2
1 2 3
4 5 6

פלט 2

-1

הערה

בדוגמה 1 אפשר, למשל, לקנות את הכרטיסים 1, 3, 6.