P8134 [ICPC 2020 WF] Opportunity Cost

ICPC2020 WF G

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 simplicity, 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^{\text{th}}$ phone, then the opportunity cost of your phone is defined as $$\max _{1 \leq i \leq n}\left(\max \left(x_{i}-x, 0\right)+\max \left(y_{i}-y, 0\right)+\max \left(z_{i}-z, 0\right)\right)$$ Write a program that, given the list of available phones, finds a phone with the minimum opportunity cost.

The first line of input contains an integer $n$ ($2 \leq n \leq 200\,000$), the number of phones considered. Following that are $n$ lines. The $i^{\text{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^{\text{th}}$ phone ($1 \leq x_i, y_i, z_i \leq 10^9$).

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