في البداية، لا يستطيع 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.