방향

처음에 스누케는 전혀 움직일 수 없다. 티켓이 $n$장 있고, $i$번째 티켓의 가격은 $p_i$이다. 스누케가 $i$번째 티켓을 사면, 모든 점 $(x, y)$와 음이 아닌 수 $t$에 대해 $(x, y)$에서 $(x + t a_i, y + t b_i)$로 이동할 수 있다. 스누케는 임의의 두 점 사이를 오갈 수 있도록 티켓을 사려고 한다. 반드시 사야 하는 티켓의 최소 총 가격을 구하라.

첫 줄에 정수 $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번, 3번, 6번 티켓을 사면 된다.