eolymp
bolt
Try our new interface for solving problems
Problems

Sports day for idlers

Sports day for idlers

Известный учитель информатики В.И., который славится не только достижениями своих учеников в программировании, но и оригинальными методами борьбы с бездельниками (приседания со стульчиком, отжимания от пола и т.п.), планирует сразу после Кубка по программированию провести лицейную спартакиаду. Каждый класс лицея должен выставить на спартакиаду команду в составе трёх учеников из числа бездельников (с точки зрения В.И.). Программа спартакиады включает в себя такие виды упражнений: подтягивание на турнике, отжимание от пола, приседания со стульчиком. Спартакиада проводится в три тура: в первом туре участники будут подтягиваться на турнике, во втором -- отжиматся от пола, в третьем -- приседать со стульчиком. Жюри спартакиады приняло решение применить рейтинговую систему. После каждого тура подводится промежуточный рейтинг команды, который определяется по сумме баллов, набранных тремя участниками команды в данном виде упражнений. После проведения трёх туров спартакиады жюри определяет общий рейтинг команды, равный сумме промежуточных рейтингов команды в каждом из трёх туров. Команда с максимальным общим рейтингом провозглашается победителем спартакиады. В виду того, что не все виды упражнений равнозначны, результат каждого из них жюри оценивает специальным способом. За каждое подтягивание участнику идёт в зачёт \textit{\textbf{X}}\textbf{ }баллов, за каждое отжимание -- \textit{\textbf{Y}}\textbf{ }баллов, за каждое приседание -- \textit{\textbf{Z}}\textbf{ }баллов. Эти критерии достаточно объективно отображают сложность выполняемых упражнений. \includegraphics{https://static.e-olymp.com/content/0d/0d586b685bf185e7bc9a357a06bf952b56adb2c7.gif} \includegraphics{https://static.e-olymp.com/content/8b/8b097a3f33f5965560cdc83e3ad6f8cccee3ff69.gif} \includegraphics{https://static.e-olymp.com/content/33/33205db59e2f7c3e3f183e436df4a4146ce98524.gif} Но при формировании команды классный руководитель самого "ленивого" 9 класса О.М. столкнулась с некоторыми трудностями. В классе учится \textit{\textbf{N}}\textbf{ }учеников, известны спортивные данные каждого из них: \textit{\textbf{A_i}}\textbf{ }-- число подтягиваний на турнике, \textit{\textbf{B_i}}\textbf{ }-- число отжиманий от пола и \textit{\textbf{C_i}}\textbf{ }-- число приседаний. Но, имея даже такие данные о каждом ученике, достаточно сложно определить состав команды. Так как одни ученики, например, хорошо подтягиваются на турнике, но плохо отжимаются, а другие наоборот. Ваша задача помочь О.М. сформировать состав команди из трёх человек так, чтобы общий рейтинг команды на спартакиаде был максимальным. \InputFile Первая строка содержит три целых числа \textit{\textbf{X, Y і Z (1 ≤ X, Y, Z ≤ 10^4)}}, разделённых одиночными пробелами. Вторая содержит целое число \textit{\textbf{N (3 ≤ N ≤ 10^5)}} -- количество учеников в классе. Каждая из последующих \textit{\textbf{N}} строк описывает спортивные данные каждого ученика класса и содержит три целых числа \textit{\textbf{A_i}}, \textit{\textbf{B_i}}\textbf{ и} \textit{\textbf{C_i (1 ≤ A_i, B_i, C_i ≤ 10^4)}}, разделённых одиночными пробелами. \OutputFile В первой строке - общий рейтинг, который могут набрать ученики, во второй - три целых числа, разделённых одиночными пробелами, -- номера учеников, которые должны попасть в команду. Ученики нумеруются последовательно, начиная с единицы в порядке ввода их данных. Если вариантов решения несколько, выведите любой из них.
Time limit 2 seconds
Memory limit 256 MiB
Input example #1
10 10 10
4
1 1 1
10 1 1
1 10 1
1 1 10
Output example #1
360
2 3 4
Input example #2
2 3 2
6
3 1 4
5 1 1
2 3 2
3 2 3
2 3 2
1 4 1
Output example #2
52
3 5 4
Input example #3
5 3 4
7
2 7 12
13 10 5
6 7 5
1 1 20
8 2 14
3 21 4
7 9 8
Output example #3
311
7 2 5