/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
平面上の N 個の相異なる格子点 (X_i, Y_i) \ (i = 1, 2, \dots, N) が与えられます． 各格子点 (X_i, Y_i) は整数の得点 P_i を持っています． これらの格子点から，以下の条件を満たすように好きな個数だけ選びます． このとき，選んだ格子点の得点の総和としてあり得る最大値を求めてください．
条件: 選ばれた格子点の凸結合に支配されるような格子点は必ず選ばれている． すなわち，各 k = 1, 2, \dots, N について，以下を満たす N 個の非負実数の組 (\lambda_1, \lambda_2, \dots, \lambda_N) が存在するならば，格子点 (X_k, Y_k) は選ばれている．
- \lambda_i > 0 \implies {}格子点 (X_i, Y_i) は選ばれている．
- \sum_{i=1}^N \lambda_i = 1
- \sum_{i=1}^N \lambda_i X_i \geq X_k
- \sum_{i=1}^N \lambda_i Y_i \geq Y_k
制約
- 1 \leq N \leq 200
- 1 \leq X_i \leq 10^9 \ \ (1 \leq i \leq N)
- 1 \leq Y_i \leq 10^9 \ \ (1 \leq i \leq N)
- (X_i, Y_i) \neq (X_j, Y_j) \ \ (i \neq j)
- |P_i| \leq 10^7 \ \ (1 \leq i \leq N)
入力
入力は以下の形式で標準入力から与えられる．
N X_1 \ Y_1 \ P_1 X_2 \ Y_2 \ P_2 \vdots X_N \ Y_N \ P_N
出力
条件を満たすように格子点を選ぶことで達成可能な得点の総和の最大値を出力せよ．
入力例 1
3 1 4 2 4 1 3 2 2 -4
出力例 1
3
(X_2, Y_2) = (4, 1) のみを選ぶのが最適です． (X_1, Y_1) = (1, 4) も選ぶ場合，たとえば \lambda_1 = 0.4,\ \lambda_2 = 0.6 とすると，
\[ \lambda_1 + \lambda_2 = 0.4 + 0.6 = 1\\[1mm] \lambda_1 X_1 + \lambda_2 X_2 = 0.4 \times 1 + 0.6 \times 4 = 2.8 \geq 2 = X_3\\[1mm] \lambda_1 Y_1 + \lambda_2 Y_2 = 0.4 \times 4 + 0.6 \times 1 = 2.2 \geq 2 = Y_3 \]
となるため，(X_3, Y_3) = (2, 2) も選ぶ必要があり，結果として損をします．
入力例 2
3 1 4 2 4 1 3 2 2 -1
出力例 2
4
すべての点を選ぶのが最適です．
入力例 3
3 1 4 2 4 1 3 1 1 -6
出力例 3
0
1 つも選ばないのが最適な場合もあります．
Score : 100 points
Problem Statement
You are given N distinct integer grid points (X_i, Y_i) \ (i = 1, 2, \dots, N) in the plane, each of which has an integer score P_i. You can choose an arbitrary number of grid points among them under the following condition. Find the maximum value of the sum of the scores of chosen grid points.
Condition: A grid point dominated by a convex combination of the chosen grid points must be chosen. That is, for each k = 1, 2, \dots, N, if there exists a tuple (\lambda_1, \lambda_2, \dots, \lambda_N) of N nonnegative reals with the following conditions, then (X_k, Y_k) is chosen:
- \lambda_i > 0 \implies (X_i, Y_i) is chosen.
- \sum_{i=1}^N \lambda_i = 1.
- \sum_{i=1}^N \lambda_i X_i \geq X_k.
- \sum_{i=1}^N \lambda_i Y_i \geq Y_k.
Constraints
- 1 \leq N \leq 200
- 1 \leq X_i \leq 10^9 \ \ (1 \leq i \leq N)
- 1 \leq Y_i \leq 10^9 \ \ (1 \leq i \leq N)
- (X_i, Y_i) \neq (X_j, Y_j) \ \ (i \neq j)
- |P_i| \leq 10^7 \ \ (1 \leq i \leq N)
Input
The input is given from Standard Input in the following format:
N X_1 \ Y_1 \ P_1 X_2 \ Y_2 \ P_2 \vdots X_N \ Y_N \ P_N
Output
Print the maximum value of the sum of the scores of grid points that are chosen under the condition.
Sample Input 1
3 1 4 2 4 1 3 2 2 -4
Sample Output 1
3
It is optimal to choose only (X_2, Y_2) = (4, 1). If you choose (X_1, Y_1) = (1, 4) in addition, then for example \lambda_1 = 0.4 and \lambda_2 = 0.6 satisfy
\[ \lambda_1 + \lambda_2 = 0.4 + 0.6 = 1\\[1mm] \lambda_1 X_1 + \lambda_2 X_2 = 0.4 \times 1 + 0.6 \times 4 = 2.8 \geq 2 = X_3\\[1mm] \lambda_1 Y_1 + \lambda_2 Y_2 = 0.4 \times 4 + 0.6 \times 1 = 2.2 \geq 2 = Y_3, \]
and hence (X_3, Y_3) = (2, 2) must be chosen in addition, which decreases the sum of scores as a result.
Sample Input 2
3 1 4 2 4 1 3 2 2 -1
Sample Output 2
4
It is optimal to choose all the grid points.
Sample Input 3
3 1 4 2 4 1 3 1 1 -6
Sample Output 3
0
It is sometimes optimal to choose no grid point.