如你所知，有些兔子是好兔子，有些兔子是坏兔子。

给定所有兔子的位置及其“善良度”权重（好兔子的权重为正整数，坏兔子的权重为负整数）。任意两只兔子不在同一位置。请使用一条直线将它们分为两组，使得直线某一侧的兔子“善良度”之和尽可能大。位于直线上的兔子会被计入直线两侧的权重和中。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 4000$)，表示兔子的数量。接下来的 $N$ 行，每行包含三个空格分隔的整数：$x_i, y_i, w_i$，表示在点 $(x_i, y_i)$ 处有一只权重为 $w_i$ 的兔子 ($-1\,000\,000 \le x_i \le 1\,000\,000; -1\,000\,000 \le y_i \le 1\,000\,000; -10\,000 \le w_i \le 10\,000$)。所有位置 $(x_i, y_i)$ 均不相同（即不存在 $j \neq i$ 使得 $(x_i, y_i) = (x_j, y_j)$）。

在总分 25 分中，有 5 分满足 $N \le 200$ 且任意三点不共线。 另有 10 分满足任意三点不共线。

输出格式

输出通过画一条直线并选取该直线某一侧的所有兔子所能得到的最大权重和。

样例

输入 1

6
1 8 4
1 4 6
7 7 2
4 10 -3
4 6 -9
4 2 8

输出 1

18

说明

选取权重为 4、6 和 8 的兔子，它们位于直线的“左侧”，如下图所示：