P14276 [ROI 2014 Day2] 电影学院

**译自 [ROI 2014](https://neerc.ifmo.ru/school/archive/2013-2014.html) Day2 T1.** ***[Киноакадемия](https://neerc.ifmo.ru/school/archive/2013-2014/ru-olymp-roi-2014-statement-day2.pdf)***

在电影学院奖的最终评选中，共有 $n$ 部 2014 年度最佳电影入围。本次评选设有两个奖项：最佳导演奖与最佳剧本奖。根据比赛规则，每个奖项必须恰好颁给一部电影，且两项奖不能颁给同一部电影。 通过对观众与影评人的大量调查，得到了以下数据：每部电影在每个奖项上获奖所能带来的“欢呼值”（即公众欢腾的程度）。细致的记者们还进一步调查了：如果某部电影在两个奖项中都未获奖，其“欢呼值”又会是多少。 请你编写程序，根据调查结果，确定通过选择获奖电影，所能获得的**最大总欢呼值**。

第一行包含一个整数 $n$ —— 入围电影的数量。 接下来 $n$ 行中，第 $i$ 行包含三个整数 $a_i$, $b_i$, $c_i$，其含义如下： - $a_i$ —— 若第 $i$ 部电影未在任何奖项中获奖时的欢呼值； - $b_i$ —— 若第 $i$ 部电影获得“最佳导演奖”时的欢呼值； - $c_i$ —— 若第 $i$ 部电影获得“最佳剧本奖”时的欢呼值。

输出共两行： - 第一行输出一个整数 —— 可以达到的最大总欢呼值； - 第二行输出两个整数 —— 分别是获得“最佳导演奖”和“最佳剧本奖”的电影编号。 电影编号为从 $1$ 到 $n$ 的自然数。若最优方案不唯一，可以输出任意一个最优方案。

### 样例解释 在样例中，最优的方案总欢呼值为 $3 + 5 + 9 = 17$。 ### 数据范围 本题包含三个子任务。每个子任务独立测试，只有当该子任务的所有测试通过时，才能获得对应分值。 | 子任务 | 分值 | 限制条件 | |:--:|:--:|:--:| | 1 | 20 | $2 \le n \le 100$，$1 \le a_i, b_i, c_i \le 10^5$ | | 2 | 25 | $2 \le n \le 2000$，$1 \le a_i, b_i, c_i \le 10^5$ | | 3 | 55 | $2 \le n \le 10^5$，$1 \le a_i, b_i, c_i \le 10^9$ |