Задача №1895. Еноты и конец, Света!
В тёмном лесу со старыми дуплистыми деревьями живут еноты. Недавно главный енот предсказал скорый конец света. Было принято решение воспрепятствовать этому с помощью магии, ведь еноты — носители тайного знания!
Еноты улеглись на полянке в лесу, при этом каждый енот улёгся в форме квадрата со сторонами, расположенными под \(45^{\circ}\) к сторонам света. Теперь для завершения ритуала всем енотам нужно вытянуть лапки так, чтобы до \(i\)-го енота могло дотянуться не менее \(k_i\) других енотов. Оказалось, что размаха лапок енотов недостаточно, поэтому главный енот приказал всем енотам тренироваться ежедневно.
Изначально размах лапок всех енотов очень мал, и енот может дотянуться только до точки, совпадающей с его центром. На следующий день это все точки, удалённые от центра не более чем на 1 по каждой из координат. За один день тренировок все еноты увеличивают размах лапок на 1, таким образом, на \(i\)-й день енотам доступны все точки, удалённые не более чем на \(i\) по каждой из осей. Считается, что енот \(A\) способен дотянуться до енота \(B\), если размаха лапок енота \(A\) достаточно, чтобы дотянуться до всех точек енота \(B\).
Определите минимальное количество дней тренировок, которое необходимо для выполнения приказа главного енота.
Первая строка ввода содержит единственное целое число \(n\) — количество енотов (\(1 \le n \le 500\,000\)). Далее следуют \(n\) строк, содержащих по четыре целых числа каждая — координаты соответствующего енота \(x_i, y_i\), его размер \(s_i\) и магическое число \(k_i\) (\(-10^5 \le x_i, y_i \le 10^5\), \(1 \le s_i \le 10^5\), \(1 \le k_i < n\)). Таким образом, \(i\)-й енот лежит в форме квадрата с координатами \((x_i-s_i, y_i)\), \((x_i, y_i-s_i)\), \((x_i+s_i, y_i)\), \((x_i, y_i+s_i)\).
Выведите одно целое число — минимальное количество дней тренировок.
3 2 2 1 2 4 5 2 2 5 1 1 2
6