The program committee must be able to correctly estimate the level of teams that will participate in the forthcoming contest and choose the problems according to that level. It is not always easy to prepare a problem set that will please both school teams and the most experienced veterans of the programming contests, who won dozens of them.
In order to make his job easier, the chairman of the program committee asked the chairman of the jury to make the eligibility rules stricter and forbid too young or too experienced teams to participate in the contest.
For each team that had applied for participation, the jury calculated the average age of its members and the number of official contests this team participated in. In addition, the program committee estimated the satisfaction that each team would get from the problem set.
The jury decided to state the eligibility rules as follows: a team is eligible to participate if and only if its average age and the number of contests it participated in
fall in certain ranges of values. It only remained to set the boundaries of these ranges so that the sum of satisfactions of the eligible teams would be as large as possible. Of course, there had to be at least two eligible teams, otherwise there would have been no sense in holding the contest.
The first line contains the number n of teams that want to participate in the contest (2 ≤ n ≤ 1500). Each of the following n lines contains three space-separated integers a, f and s (4·108 ≤ a ≤ 109; 0 ≤ f, |s| ≤ 109). They are the average age of participants (in seconds), the number of official contests the team participated in, and the satisfaction that the team will get from the problem set, respectively.
In the first line output the minimal and maximal admissible average age of participants. In the second line output the minimal and maximal admissible number of contests. All these numbers must be nonnegative integers and must not exceed 109. If there are several possible answers, output any of them.
500000000 1 1
510000000 3 -10
600000000 3 2
700000000 4 3
Problem Author: Sergey Pupyrev (prepared by Alex Samsonov)
Problem Source: NEERC 2009, Eastern subregional contest