You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

人工智能（$\texttt{ai}$）

【题目描述】

小 D 创造出了一个聪明绝顶的 AI。

这天，小 D 想和这个 AI 玩一个游戏，因此他准备了 $n$ 种石子，第 $i$ 种石子有 $a_i$ 个，小 D 每得到 $p_i$ 个这种石子就能获得 $w_i$ 的分数。

小 D 和 AI 会轮流取石子，每人取走恰好一颗，直到没有石子，小 D 想最大化自己的分数，而 AI 要最小化小 D 的分数。

但小 D 觉得这个问题太简单了，于是他想把石子平分成两堆（保证石子总数是偶数），在两堆石子中分别独立地做这个游戏。

在第一个游戏中，小 D 先手，而第二个游戏中 AI 先手，最终小 D 的分数是两个游戏里的分数和。

假设双方目标不变且都足够聪明，小 D 想知道自己最终的分数是多少。

【输入格式】

从 $\texttt{ai.in}$ 中读入数据。

第一行一个整数 $n$ ，表示石子的种类数。

接下来 $n$ 行，每行三个整数 $a_i,p_i,w_i$，含义如题所述。

【输出格式】

一行一个整数表示最终小 D 的分数。

【样例 1 输入】

4
11 3 10
8 4 8
7 3 2
10 4 5

【样例 1 输出】

35

【数据范围】

对于所有测试数据保证：$1\le n\le 2000,\sum a_i\le 10^6,\sum p_i\le 2000,w_i\le 10^9,p_i,a_i,w_i\ge 1$ 且 $\sum a_i$ 为偶数。