最初，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 张票。