e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

I Cup Alexandria 2010

Sports day for idlers

Известный учитель информатики В.И., который славится не только достижениями своих учеников в программировании, но и оригинальными методами борьбы с бездельниками (приседания со стульчиком, отжимания от пола и т.п.), планирует сразу после Кубка по программированию провести лицейную спартакиаду. Каждый класс лицея должен выставить на спартакиаду команду в составе трёх учеников из числа бездельников (с точки зрения В.И.). Программа спартакиады включает в себя такие виды упражнений: подтягивание на турнике, отжимание от пола, приседания со стульчиком. Спартакиада проводится в три тура: в первом туре участники будут подтягиваться на турнике, во втором – отжиматся от пола, в третьем – приседать со стульчиком.

Жюри спартакиады приняло решение применить рейтинговую систему.

После каждого тура подводится промежуточный рейтинг команды, который определяется по сумме баллов, набранных тремя участниками команды в данном виде упражнений. После проведения трёх туров спартакиады жюри определяет общий рейтинг команды, равный сумме промежуточных рейтингов команды в каждом из трёх туров. Команда с максимальным общим рейтингом провозглашается победителем спартакиады.

В виду того, что не все виды упражнений равнозначны, результат каждого из них жюри оценивает специальным способом. За каждое подтягивание участнику идёт в зачёт Xбаллов, за каждое отжимание – Yбаллов, за каждое приседание – Zбаллов. Эти критерии достаточно объективно отображают сложность выполняемых упражнений.

prb1345-1prb1345-2prb1345-3

Но при формировании команды классный руководитель самого "ленивого" 9 класса О.М. столкнулась с некоторыми трудностями. В классе учится Nучеников, известны спортивные данные каждого из них: Ai– число подтягиваний на турнике, Bi– число отжиманий от пола и Ci– число приседаний. Но, имея даже такие данные о каждом ученике, достаточно сложно определить состав команды. Так как одни ученики, например, хорошо подтягиваются на турнике, но плохо отжимаются, а другие наоборот. Ваша задача помочь О.М. сформировать состав команди из трёх человек так, чтобы общий рейтинг команды на спартакиаде был максимальным.

Входные данные

Первая строка содержит три целых числа X, Y і Z (1 ≤ X, Y, Z ≤ 104), разделённых одиночными пробелами.

Вторая содержит целое число N (3 ≤ N ≤ 105) – количество учеников в классе.

Каждая из последующих N строк описывает спортивные данные каждого ученика класса и содержит три целых числа Ai, Bi иCi (1 ≤ Ai, Bi, Ci ≤ 104), разделённых одиночными пробелами.

Выходные данные

В первой строке - общий рейтинг, который могут набрать ученики, во второй - три целых числа, разделённых одиночными пробелами, – номера учеников, которые должны попасть в команду. Ученики нумеруются последовательно, начиная с единицы в порядке ввода их данных. Если вариантов решения несколько, выведите любой из них.

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