ICPC 2020 · Problem G · Opportunity Cost

Time limit: 5 seconds

As with most types of products, buying a new phone can be difficult. One of the main challenges is that there are a lot of different aspects of the phone that you might care about, such as its price, its performance, and how user-friendly the phone is. Typically, there will be no single phone that is simultaneously the best at all of these things: the cheapest phone, the most powerful phone, and the most user-friendly phone will likely be different phones.

Thus when buying a phone, you are forced to make some sacrifices by balancing the different aspects you care about against each other and choosing the phone that achieves the best compromise (where “best” of course depends on what your priorities happen to be). One way of measuring this sacrifice is known as the opportunity cost, which (for the purposes of this problem) we define as follows.

Suppose that you have bought a phone with price $x$, performance $y$, and user-friendliness $z$. For sim- plicity, we assume that these three values are measured on a comparable numeric scale where higher is better. If there are $n$ available phones, and the values $(x_{i}, y_{i}, z_{i})$ represent the (price, performance, user-friendliness) of the $i$th phone, then the opportunity cost of your phone is defined as

$max$ $1\le i\le n (max(x^{i}- x,0) + max(y^{i}- y,0) + max(z^{i}- z,0)).$

Write a program that, given the list of available phones, finds a phone with the minimum opportunity cost.

Input

The first line of input contains an integer $n$ ($2 \le n \le 200 000$), the number of phones considered. Following that are $n$ lines. The $i$th of these lines contains three integers $x_{i}$, $y_{i}$, and $z_{i}$, where $x_{i}$ is the price, $y_{i}$ is the performance, and $z_{i}$ is the user-friendliness of the $i$th phone ($1\le xi, yi, zi \le 10^{9}$).

Output

Output a single line containing two integers: the smallest possible opportunity cost and an integer be- tween $1$ and $n$ indicating the phone achieving that opportunity cost. If there are multiple such phones, output the one with the smallest index.

Sample Input 1

4
20 5 5
5 20 5
5 5 20
10 10 10

Sample Output 1

10 4

ICPC World Finals 2020 Problem G: Opportunity Cost

Sample Input 2

4
15 15 5
5 15 15
15 5 15
10 10 10

Sample Output 2

10 1

ICPC World Finals 2020 Problem G: Opportunity Cost