### 问题描述 可可和乐乐在玩一个策略游戏，游戏中有一套卡片，共 $ T $ 种不同的类型。每种类型的卡片有 $ q_i $ 张，每 $ a_i $ 张同类型的卡片可以组合成 $ v_i $ 分。游戏开始时，所有卡片被平均分成两堆，每堆有 $ \frac{N}{2} $ 张卡片。可可首先从第一堆中选择卡片，然后乐乐选择，直到这堆卡片被选完；接着，乐乐先从第二堆中选择卡片，然后可可选择，直到第二堆卡片也被选完。可可的目标是最大化自己的得分，而乐乐则试图使可可的得分最小化。如果双方都采取最优策略，求可可能获得的最大分数。 ### 输入格式 第一行包含一个整数 $ T $，代表卡片类型的数量。 接下来的 $ T $ 行，每行包含三个由空格分隔的整数 $ a_i $、$ q_i $ 和 $ v_i $。 ### 输出格式 输出一个整数，为可可在双方都采取最优策略时可能获得的最大分数。 ### 样例输入 ``` 1 7 26 2261 ``` ### 样例输出 ``` 2261 ``` ### 评测数据规模 - $ 1 \leq T \leq 2000 $ - $ 1 \leq a_i \leq N \leq 2000 $，$ N $ 为所有卡片的总数 - $ 1 \leq v_i \leq 3000 $ - $ 1 \leq q_i \leq 500000 $ - $ \sum q_i $ 为偶数