시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 9 | 7 | 7 | 77.778% |
В финал конкурса Киноакадемии вышли $n$ лучших кинофильмов 2014 года. В конкурсе награждаются фильмы в двух номинациях: лучшая режиссура и лучший сценарий. По правилам конкурса в каждой номинации должен быть награжден ровно один фильм, причём в разных номинациях --- разные фильмы.
В ходе многочисленных опросов зрителей и кинокритиков удалось собрать данные, показывающие, какой уровень ликования вызовет победа каждого фильма в каждой из номинаций. Дотошные журналисты на этом не остановились и дополнительно выяснили, каким будет уровень ликования, если тот или иной фильм не выиграет ни в одной из номинаций.
Требуется написать программу, которая по результатам опросов определяет наибольший суммарный уровень ликования, которого можно добиться выбором фильмов для награждения в указанных номинациях.
В первой строке входного файла задано целое число $n$ --- количество кинофильмов, участвующих в финале конкурса Киноакадемии. В следующих $n$ строках содержатся по три целых числа $a_i$, $b_i$, $c_i$ --- уровень ликования, если $i$-й фильм не выиграет ни в одной из номинаций, уровень ликования, если этот фильм выиграет в номинации на лучшую режиссуру, и уровень ликования, если этот фильм выиграет в номинации на лучший сценарий.
Первая строка выходного файла должна содержать одно число --- наибольший возможный суммарный уровень ликования. Вторая строка должна содержать два целых числа --- номера фильмов-победителей в номинациях лучшая режиссура и лучший сценарий соответственно. Фильмы нумеруются натуральными числами от 1 до $n$. Если оптимальных способов выбора награждаемых фильмов несколько, можно вывести любой из них.
3 3 6 9 1 5 7 1 3 9
17 2 3
В приведенном примере наибольший суммарный уровень ликования равен $3 + 5 + 9 = 17$.