Спочатку 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.