题目描述

旅行者与派蒙正在提瓦特大陆上进行一场卡牌游戏。共有 $T$ 种元素卡牌，每集齐 $a_i$ 张第 $i$ 种元素卡牌，就可以获得 $v_i$ 点元素能量。第 $i$ 种元素卡牌总共有 $q_i$ 张。双方都清楚所有卡牌的数量。游戏规则如下：

• 旅行者先将全部 $N = q_1 + q_2 + \dots + q_T$ 张卡牌均分为两堆，每堆恰好 $\dfrac{N}{2}$ 张，并自行指定哪一堆为牌堆 A，哪一堆为牌堆 B。
• 两人轮流从牌堆 A 中取牌，由旅行者先手。取完后，两人根据各自在牌堆 A 中获得的卡牌计算元素能量，并计入总能量。
• 接着两人轮流从牌堆 B 中取牌，由派蒙先手。取完后，两人仅根据各自在牌堆 B 中获得的卡牌计算元素能量（不叠加牌堆 A 的卡牌），并计入总能量。

旅行者希望最大化自己获得的总元素能量，而派蒙会尽力最小化旅行者的能量。若两人均采取最优策略，求旅行者最终能获得的最大元素能量。

输入格式

第一行一个整数 $T$，表示元素卡牌的种类数。

接下来 $T$ 行，每行三个用空格分隔的整数，第 $i$ 行包含 $a_i, q_i, v_i$。

输出格式

输出一个整数，表示在双方均采取最优策略时，旅行者能获得的最大元素能量。

样例1

样例输入

1
7 26 2261

样例输出

2261

样例1解释

在该样例中，所有卡牌只能均分为两堆，每堆 13 张。

无论两人如何取牌，结果固定：

• 牌堆 A 中旅行者拿到 7 张该卡牌，获得 $\left\lfloor \dfrac{7}{7} \right\rfloor \times 2261 = 2261$ 点能量。
• 牌堆 B 中旅行者只拿到 6 张该卡牌，获得 $\left\lfloor \dfrac{6}{7} \right\rfloor \times 2261 = 0$ 点能量。

旅行者总能量为 $2261 + 0 = 2261$。

样例2

样例输入

2
3 6 7
2 4 8

样例输出

15

样例2解释

旅行者应将卡牌分为：

• 牌堆 A：5 张第一种元素牌；
• 牌堆 B：1 张第一种元素牌 + 4 张第二种元素牌。

在牌堆 A 中，旅行者获得 3 张第一种卡牌，得到 $\left\lfloor \dfrac{3}{3} \right\rfloor \cdot 7 = 7$ 点能量。 在牌堆 B 中，派蒙最优操作下，旅行者获得 2 张第二种卡牌，得到 $\left\lfloor \dfrac{2}{2} \right\rfloor \cdot 8 = 8$ 点能量。

总能量为 $7 + 8 = 15$。

数据范围

所有数据满足：

• $1 \leq T \leq 2\ 000$
• $\sum\limits_{i=1}^T a_i \leq 2\ 000$
• $\sum\limits_{i=1}^T q_i \leq 500\ 000$
• $\sum\limits_{i=1}^T q_i$ 为偶数
• $1\leq a_i,q_i$
• $1 \leq v_i \leq 3\ 000$

子任务 1（30 分）：$\sum q_i \le 5\ 000$ 子任务 2（70 分）：无特殊限制