Minimum Opportunity Cost Phone

Buying a new phone can be a challenge since no single phone is best in all categories (price, performance, and user-friendliness). In this problem, each phone is described by three numeric values \(x\), \(y\), and \(z\) respectively, with higher values preferred. The opportunity cost of choosing a phone with values \((x,y,z)\) is defined as:

[ \max_{1 \leq i \leq n} \Big(\max(x_i - x, 0) + \max(y_i - y, 0) + \max(z_i - z, 0)\Big)]

You are given \(n\) available phones with characteristics \((x_i, y_i, z_i)\) for \(1 \le i \le n\). Your task is to find a phone which minimizes the opportunity cost as defined above, and output the minimum opportunity cost value.

inputFormat

The first line contains an integer \(n\) representing the number of available phones. \(n\) lines follow, each containing three space-separated integers \(x\), \(y\), and \(z\) which denote the phone's price, performance, and user-friendliness respectively.

outputFormat

Output a single integer, which is the minimum opportunity cost among all the phones.

sample

3
1 2 3
2 2 2
3 2 1

1