D2-Lsxszc打比赛（cmpe）

题目背景

Lsxszc为了在彻底退役之前获得luogu红名，决定一直参加公开赛直到比赛分打满。贴心的kkkw决定给他一点帮助，他给了Lsxszc一个时间曲解装置$\dots$

题目描述

时间被曲解，不再有天数，小时，分钟，秒的概念。取而代之的是单位oOo。

共有 $n$ 场公开赛。你可以任意选择参加比赛的顺序，但是必须连续打，且必须打完所有比赛。假设每场比赛需要 $M_i$ 的时间参加，当你在第 $k$ oOo 参加第 $i$ 场比赛，则会在 $k+M_i$ oOo 结束比赛，并需要立即参加下一场比赛。

但是Lsxszc的实力具有二象性。具体来说，假设他在第 $k$ oOo 参加第 $i$ 场比赛，若 $k$ 为奇数，则可以获得 $x_i$ 的等级分，若 $k$ 为偶数，则可以获得 $y_i$ 的等级分。

Lsxszc比较懒，他打算在任意大于第 $0$ oOo的时间开始比赛旅程，求最后他可以得到的等级分最大值。

输入格式

$N$

$W_1 \ \ x_1 \ \ x_2$

$\dots$

$W_n \ \ x_n \ \ y_n$

输出格式

一行一个整数，表示最大得分。

输入输出样例 #1

输入 #1

3
10 1 2
20 9 7
13 11 17

输出 #1

28

输入输出样例 #2

输入 #2

4
1 1 2
2 5 7
3 9 12
4 19 15

输出 #2

39

说明/提示

对于部分测试点：

特殊性质A：所有 $M_i$ 都是偶数。

数据范围：

对于所有测试点：

• $1 \le n \le 10^5$

• $1 \le W_i,x_i,y_i\le 10^9$

后记

Lsxszc发现在还原的时间线里自己在10秒内AK了 $10^5$ 场线上赛，被棕名处理。