Covering Saplings with Three Square Films

A farmer planted N saplings on a mountainside. When winter came, the temperature dropped rapidly and the fragile saplings were in danger. To save them, the farmer decided to cover all the saplings with 3 square plastic films of size \(L\times L\). The films must be placed with their sides parallel to the coordinate axes in a 2D plane. A sapling is considered covered if it lies inside or on the boundary of a square. Given the coordinates \((X_i,Y_i)\) of the N saplings, your task is to determine the minimum possible \(L\) so that 3 squares of side length \(L\) can cover all the saplings.

Note: A set of points can be covered by a square of side \(L\) if and only if the difference between the maximum and minimum x-coordinates is no more than \(L\) and the difference between the maximum and minimum y-coordinates is no more than \(L\).

inputFormat

The first line contains an integer \(N\) (\(1 \leq N \leq 15\)), the number of saplings. Each of the following \(N\) lines contains two integers \(X_i\) and \(Y_i\), representing the coordinates of the i-th sapling.

It is guaranteed that all coordinates are integers.

outputFormat

Output a single integer, the minimum possible \(L\) such that three \(L\times L\) squares (with sides parallel to the axes) can cover all saplings.

sample

1
0 0

0