题目描述

大家都知道，有些小兔子是乖乖兔，有些则是调皮兔。

现在给你所有小兔子的位置和它们的“乖乖值”（好兔子是正数，坏兔子是负数）。保证没有两只兔子在同一个点。你要用一条直线把它们分成两组，使得一边所有兔子的“乖乖值”加起来尽可能大。注意，恰好在直线上的兔子会同时算在两边的和里哦。

输入格式

第一行输入 $N\ (2 \le N \le 4000)$，表示兔子的数量。接下来 $N$ 行，每行三个整数：$x_i\ y_i\ w_i$，表示坐标 $(x_i, y_i)$ 上有一只“乖乖值”为 $w_i\ (-10^6 \le x_i \le 10^6; -10^6 \le y_i \le 10^6; -10\,000 \le w_i \le 10\,000)$ 的兔子。所有位置 $(x_i, y_i)$ 都不重复（也就是说不存在 $j \ne i$ 使得 $(x_i, y_i) = (x_j, y_j)$）。

对于 $25$ 分中的 $5$ 分，保证 $N\le200$ 且没有三个点共线。

对于 $25$ 分中另外的 $10$ 分，同样保证没有三个点共线。

输出格式

输出一条直线，使得选取直线一侧所有兔子的“乖乖值”之和最大，输出这个最大值。

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

18

提示

比如图中，选取“乖乖值”为 $4$、$6$ 和 $8$ 的兔子，它们都在直线的“左侧”，这样加起来的和就是最大了：

翻译来源：GPT 4.1 mini。