기회비용

대부분의 제품이 그렇듯, 새 휴대폰을 사는 일은 어려울 수 있다. 어려움의 주된 원인 중 하나는 휴대폰에서 고려할 만한 측면이 가격, 성능, 사용 편의성 등 매우 다양하다는 점이다. 보통 이 모든 측면에서 동시에 가장 뛰어난 휴대폰은 존재하지 않는다. 가장 저렴한 휴대폰, 가장 성능이 좋은 휴대폰, 가장 사용하기 편한 휴대폰은 서로 다른 휴대폰일 가능성이 크다.

따라서 휴대폰을 살 때는 고려하는 여러 측면을 서로 저울질하며 어떤 부분을 포기할지 결정하고, 가장 좋은 타협점을 이루는 휴대폰을 골라야 한다. 여기서 "가장 좋은"은 물론 자신이 무엇을 우선하는지에 따라 달라진다. 이러한 포기의 정도를 측정하는 방법 중 하나가 기회비용이며, 이 문제에서는 다음과 같이 정의한다.

가격 $x$, 성능 $y$, 사용 편의성 $z$인 휴대폰을 샀다고 하자. 세 값은 모두 높을수록 좋은, 서로 비교 가능한 수치 척도로 측정된다고 가정한다. 구매 가능한 휴대폰이 $n$대이고, $i$번째 휴대폰의 (가격, 성능, 사용 편의성)을 나타내는 값이 $(x_i, y_i, z_i)$라면, 자신이 산 휴대폰의 기회비용은 다음과 같이 정의된다.

$\max_{1 \le i \le n}{\left( \max{(x_i - x, 0)} + \max{(y_i - y, 0)} + \max{(z_i - z, 0)} \right)}\text{.}$

구매 가능한 휴대폰의 목록이 주어졌을 때, 기회비용이 최소인 휴대폰을 찾는 프로그램을 작성하라.

첫째 줄에 정수 $n$이 주어진다. $n$은 고려하는 휴대폰의 수이다. ($2 \le n \le 200\,000$) 이어서 $n$개의 줄이 주어진다. 이 중 $i$번째 줄에는 세 정수 $x_i$, $y_i$, $z_i$가 주어지며, 각각 $i$번째 휴대폰의 가격, 성능, 사용 편의성이다. ($1 \le x_i, y_i, z_i \le 10^9$)

한 줄에 두 정수를 출력한다. 첫 번째는 가능한 가장 작은 기회비용이고, 두 번째는 그 기회비용을 달성하는 휴대폰의 번호이다. 번호는 1 이상 $n$ 이하이다. 그러한 휴대폰이 여러 대라면 번호가 가장 작은 휴대폰을 출력한다.