Задача №112328. Киноакадемия
В ходе многочисленных опросов зрителей и кинокритиков удалось собрать данные, показывающие, какой уровень ликования вызовет победа каждого фильма в каждой из номинаций. Дотошные журналисты на этом не остановились и дополнительно выяснили, каким будет уровень ликования, если тот или иной фильм не выиграет ни в одной из номинаций.
Требуется написать программу, которая по результатам опросов определяет наибольший суммарный уровень ликования, которого можно добиться выбором фильмов для награждения в указанных номинациях.
В первой строке входного файла задано целое число n — количество кинофильмов, участвующих в финале конкурса Киноакадемии. В следующих n строках содержатся по три целых числа \(a_i\) , \(b_i\) , \(c_i\) — уровень ликования, если \(i\)-й фильм не выиграет ни в одной из номинаций, уровень ликования, если этот фильм выиграет в номинации на лучшую режиссуру, и уровень ликования, если этот фильм выиграет в номинации на лучший сценарий.
Первая строка выходного файла должна содержать одно число — наибольший возможный суммарный уровень ликования. Вторая строка должна содержать два целых числа — номера фильмов-победителей в номинациях лучшая режиссура и лучший сценарий соответственно. Фильмы нумеруются натуральными числами от 1 до \(n\). Если оптимальных способов выбора награждаемых фильмов несколько, можно вывести любой из них.
2 <= \(n\) <= 100
1 <= \(a_i\), \(b_i\), \(c_i\) <= \(10^5\)
Подзадача оценивается в 20 баллов
2 <= \(n\) <= 2000
1 <= \(a_i\), \(b_i\), \(c_i\) <= \(10^5\)
Подзадача оценивается в 25 баллов
2 <= \(n\) <= \(10^5\)
1 <= \(a_i\), \(b_i\), \(c_i\) <= \(10^9\)
Подзадача оценивается в 55 баллов
В приведенном примере наибольший суммарный уровень ликования равен 3 + 5 + 9 = 17.
3 3 6 9 1 5 7 1 3 9
17 2 3