The Optimal Team#1345
A renowned computer science teacher, V.I., is known not only for his students' successes in programming, but also for his original methods of motivating slackers (such as squats with a chair, push-ups, etc.). He plans to organize a school sports competition right after the Programming Cup. Each class must assemble a team of three students, selected from those V.I. considers slackers, to participate in the competition.
The sports program consists of three exercises: pull-ups (on a bar), push-ups (from the floor), and squats (with a chair). The competition is held in three rounds: in the first round, participants perform pull-ups, in the second — push-ups, and in the third — squats.
The competition jury uses a points system. After each round, an interim team rating is calculated as the sum of the points earned by the three team members in that round. After all three rounds, the overall team rating equals the sum of the interim ratings from each round. The team with the highest overall rating wins the competition.
Because each type of exercise has a different relative difficulty, the jury rates the exercises differently. Each pull-up counts for points, each push-up for points, and each squat for points. These criteria fairly reflect the difficulty of each exercise.
However, the class teacher O.M. of the "laziest" 9th grade class found it challenging to select a team. The class has students, and for each one, their sports results are known: A_i (pull-ups), B_i (push-ups), and C_i (squats). Even knowing this data, selecting the best team is not trivial: some students are good at pull-ups but poor at push-ups, and vice versa for others.
Your task is to help O.M. choose three students such that the total competition rating for the team (according to the above rules) is maximized.
The first line contains three integers , , and (1 \le X, Y, Z \le 10^4), separated by spaces.
The second line contains a single integer (3 \le N \le 10^5) — the number of students in the class.
Each of the next lines contains three integers A_i, B_i, and C_i (1 \le A_i, B_i, C_i \le 10^4) — denoting the number of pull-ups, push-ups, and squats performed by the -th student.
On the first line, output the maximum total team rating achievable.
On the second line, output three distinct integers — the indices of the students selected for the team, in any order. Students are numbered from in the order their data is given.
If there are multiple solutions, output any of them.
Example 1
Example 2
Example 3