题目描述

译自 CCO 2016 Day1 T2「Splitting Hares」。

不好啦，那些坏心眼的兔子又来了！这次它们分成了两拨，一拨善良的，一拨邪恶的。

你知道每个兔子的位置和它们代表的善意值：好兔子是正数，坏兔子是负数。没有两只兔子会在同一个地方。 现在你要用一条直线把它们分成两组，让一边的兔子善意值总和尽可能大。这条直线上的兔子，它的善意值会同时算到两边去。

输入格式

第一行包含一个整数 $N$，表示兔子数量。接下来 $N$ 行，每行包含三个空格分隔的整数 $x_i,y_i,w_i$，表示在坐标 $(x_i, y_i)$ 的地方有一只兔子，它的善意值是 $w_i$。每个兔子的坐标都是唯一的，也就是说不会有两行的 $(x_i, y_i)$ 相同。

输出格式

输出一个整数，表示你能通过画一条直线分兔子，并且让一边的兔子善意值总和最大的值。

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

18

如上图所示，我们选择善意值为 $4,6,8$ 的兔子，因为它们都在直线的左边。

数据范围与提示

对于 $20\%$ 的数据，$N \leq 200$；
对于另外 $40\%$ 的数据，不存在三点共线；
对于 $100\%$ 的数据，$2\leq N \leq 4000$，$-10^6\leq x_i,y_i\leq 10^6, -10^4 \leq w_i\leq 10^4$。