Научимся считать за константу opportunity cost для каждого tuple (x, y, z). Opportunity cost для (x, y, z) равен max по i=1...n величины max(x[i] - x, 0) + max(y[i] - y, 0) + max(z[i] - z, 0). Покажем что не нужно пробегать все i, а только следующий индексы: Пусть индексы m1, m2, m3, m4, m5, m6, m7 такие что m1 максимизирует x[m] m2 максимизирует y[m] m3 максимизирует z[m] m4 максимизирует x[m] + y[m] m5 максимизирует y[m] + z[m] m6 максимизирует x[m] + z[m] m7 максимизирует x[m] + y[m] + z[m]. То есть например, y[m5] + z[m5] максимален среди y[i] + z[i] для любых i.

Докажем что максимум opportunity cost для произвольного (x, y, z) достигается на одном из m1, m2, m3, m4, m5, m6, m7. Пусть он достигся на i вот собственно он OC[i] = max(x[i] - x, 0) + max(y[i] - y, 0) + max(z[i] - z, 0), к примеру, пусть первый максимум при этом был нулем, второй и третий не нулевыми (остальные случаи аналогичны). Тогда OC[i] = 0 + (y[i] - y) + (z[i] - z) = y[i] + z[i] - y - z <= y[m5] + z[m5] - y - z = 0 + (y[m5] - y) + (z[m5] - z) <= max(x[m5] - x, 0) + max(y[m5] - y, 0) + max(z[m5] - z, 0) = OC[m5]. Последнее неравенство в силу a <= max(a, b) и b <= max(a, b). То есть получили что на m5 opportunity cost не меньше, а значит и максимизирующий i это m5.

То есть для каждого (x, y, z) если считаем за константу opporunity cost. Осталось посчитать для всех и найти наименьший.