题目背景

译自 ROI 2014 Day2 T1. Киноакадемия

题目描述

在电影学院奖的最终评选中，共有 $n$ 部 2014 年度最佳电影入围。本次评选设有两个奖项：最佳导演奖与最佳剧本奖。根据比赛规则，每个奖项必须恰好颁给一部电影，且两项奖不能颁给同一部电影。

通过对观众与影评人的大量调查，得到了以下数据：每部电影在每个奖项上获奖所能带来的“欢呼值”（即公众欢腾的程度）。细致的记者们还进一步调查了：如果某部电影在两个奖项中都未获奖，其“欢呼值”又会是多少。

请你编写程序，根据调查结果，确定通过选择获奖电影，所能获得的最大总欢呼值。

输入格式

第一行包含一个整数 $n$ —— 入围电影的数量。

接下来 $n$ 行中，第 $i$ 行包含三个整数 $a_i$, $b_i$, $c_i$，其含义如下：

• $a_i$ —— 若第 $i$ 部电影未在任何奖项中获奖时的欢呼值；
• $b_i$ —— 若第 $i$ 部电影获得“最佳导演奖”时的欢呼值；
• $c_i$ —— 若第 $i$ 部电影获得“最佳剧本奖”时的欢呼值。

输出格式

输出共两行：

• 第一行输出一个整数 —— 可以达到的最大总欢呼值；
• 第二行输出两个整数 —— 分别是获得“最佳导演奖”和“最佳剧本奖”的电影编号。

电影编号为从 $1$ 到 $n$ 的自然数。若最优方案不唯一，可以输出任意一个最优方案。

3
3 6 9
1 5 7
1 3 9

17
2 3

提示

样例解释

在样例中，最优的方案总欢呼值为 $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$