| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 512 MB | 36 | 13 | 13 | 40.625% |
Initially, Snuke can’t move at all. There are n tickets, and the price of the i-th ticket is pi. If Snuke buys the i-th ticket, for all points (x, y) and a nonnegative number t, he can move from (x, y) to (x + tai, y + tbi). Snuke wants to buy tickets and he wants to be able to travel between any two points. Compute the minimal possible total price of the tickets he must buy.
First line of the input contains one integer n (1 ≤ n ≤ 2 · 105). Then n lines follow; i’th of these lines contains three integers ai, bi, pi (−109 ≤ ai, bi ≤ 109, 1 ≤ pi ≤ 109).
Print the minimal possible total price of the tickets he must buy in order to be able to move between any two points. If this is impossible, print −1 instead.
7 0 3 1 0 3 2 1 -1 2 0 0 1 -2 4 1 -4 0 1 2 1 2
4
2 1 2 3 4 5 6
-1
In the Sample 1 you can, for example, buy tickets 1, 3, 6.