AT1202Contest_i Convex Dombination

给定平面上的 $ 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) $ ### Sample Explanation 1 $ (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) $ も選ぶ必要があり，結果として損をします． ### Sample Explanation 2 すべての点を選ぶのが最適です． ### Sample Explanation 3 $ 1 $ つも選ばないのが最適な場合もあります．