Манхетенське парування

Вхідні дані

У першому рядку задано одне ціле число $n$ $(1 \leq n \leq 1 0^{5})$ (1 \le n \le 10^5).

У наступних $2 \cdot n$ 2\cdot n рядках задано по два цілих числа $x_{i}$ x_i, $y_{i}$ y_i $(0 \leq x_{i} \leq 1 0^{9}, 0 \leq y_{i} \leq 1)$ (0 \le x_i \le 10^9, 0 \le y_i\le 1) — координати відповідної точки.

Вихідні дані

Виведіть одне ціле число — максимальну манхетенську відстань між точками однієї пари в оптимальному розбитті.

Приклади

Приклад 1

Loading

Приклад 2

Loading

Приклад 3

Loading

Примітка

У другому прикладі розбиття на пари $[(18, 0), (14, 0)]$ [(18, 0), (14, 0)], $[(3, 0), (1, 0)]$ [(3, 0), (1, 0)] та $[(8, 0), (10, 0)]$ [(8, 0), (10, 0)] є єдиним оптимальним розбиттям. Манхетенські відстані між точками однієї пари в такому розбитті рівні $4$ , $2$ та $2$ , відповідно.

У третьому прикладі розбиття на пари $[(0, 1), (2, 1)]$ [(0, 1), (2, 1)], $[(2, 1), (3, 0)]$ [(2, 1), (3, 0)], $[(3, 0), (5, 0)]$ [(3, 0), (5, 0)] та $[(5, 1), (6, 0)]$ [(5, 1), (6, 0)] є оптимальним розбиттям. Усі манхетенські відстані між точками однієї пари в такому розбитті рівні $2$ .

Малюнок до третього прикладу

Оцінювання

( $2$ бали): $n = 1$ n = 1;
( $3$ бали): $x_{i} = 0$ x_i = 0 для $1 \leq i \leq 2 \cdot n$ 1 \le i \le 2\cdot n;
( $4$ бали): $n \leq 4$ n \le 4;
( $11$ балів): $n \leq 10$ n \le 10;
( $14$ балів): $y_{i} = 0$ y_i = 0 для $1 \leq i \leq 2 \cdot n$ 1 \le i \le 2\cdot n;
( $10$ балів): $x_{i} \neq = x_{j}$ x_i \neq x_j для $1 \leq i < j \leq 2 \cdot n$ 1 \le i < j \le 2\cdot n;
( $29$ балів): $n \leq 1000$ n \le 1000;
( $27$ балів): без додаткових обмежень.