题目描述
给出 $n$ 种石子，第 $i$ 种有 $a_i$ 个。保证 $\sum a_i$ 是偶数。
A 把这些石子平均分为两堆，然后按顺序执行以下操作：
- AB 两人轮流在第一堆里取一颗石子，直到取完，A 先手。
- AB 两人轮流在第二堆里取一颗石子，直到取完，B 先手。
设 A 最终得到 $b_i$ 颗第 $i$ 种石子，A 希望最大化 $S$，B 希望最小化 $S$，其中：
$$ S=\sum \lfloor\dfrac{b_i}{p_i}\rfloor\times val_i $$
求 $S$ 的值。
输入格式
第一行一个正整数 $n$。
接下来 $n$ 行，每行三个正整数 $a_i,p_i,val_i$。
输出格式
一行一个整数，为 $S$ 的值。
样例
输入
2
5 2 10
5 2 8输出
18数据范围
$1\le n\le 10$，$1\le a_i\le 2000$，$1\le p_i\le 2000$，$\prod (a_i+1)\le 200\color{red}{1}$，$1\le val_i\le 3000$