On the far-away planet L1, aliens have built an enormous city that extends towards the sky as well as on the ground.

The city has many points of interest, such as houses, offices or shops. Each is specified by three-dimensional coordinates (x,y,z).

Interestingly, the aliens use vehicles that can only move along one direction at the time. Therefore, the time taken to go from point (x,y,z) to (x',y',z') is given by the formula:

| x - x' | + | y - y' | + | z - z' |.

For example, the time to travel between (1,2,3) and (3,2,1) is 2+0+2 = 4.

Your task is to find the maximum time it takes to travel between any two points of interest of the city. There is one complication: the city is huge...

Input

The first line of the input contains an integer N (2 <= N <= 100,000) with the number of points of interest. The rest of the input is a sequence of N lines. Each line gives three integers x, y, z (-10,000 <= x,y,z <= +10,000) describing the coordinates of a point of interest of the city.

Output

An integer representing the maximum time it takes to travel between any two points of interest of the city.

Example

Input:
3
-1 0 0
0 0 0
0 0 1

Output:
2