ICAMPSEQ - IOICamp Sequence

Let's say we have 4 N-elements sequences of real numbers: A[], B[], C[], D[] .
Funtion F(i, j) is defined: F(i, j) = |Ai - Aj| + |Bi - Bj| + |Ci - Cj| + |Di - Dj| (1 ≤ i, j ≤ N).
Your task is very easy: you have to find the maximum of F(i, j).

Input

The first line: N (N ≤ 100000).
Following are N lines: the i-th line contains four real numbers Ai, Bi, Ci, Di. (-109 ≤ Ai, Bi, Ci, Di ≤ 109)

Output

Only one line is the maximum of F(i, j).
(The result takes exactly 3 decimal places)

Example

Input:
2
1.0 1.0 2.0 0.5
1.0 1.0 0.5 2.0

Output:
3.000

Added by:Nghia Nguyen Hoang
Date:2007-09-18
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:IOICamp and Ms. Thanh Vy Hua Le

hide comments
2010-04-22 13:58:08 Shaka Shadows
Time limit is too strict!!! My solution runs in O(n) and gets TLE.
2009-10-08 08:35:05 Nghia Nguyen Hoang
3.236
2009-11-21 13:23:00 monkeyvu
what will be displayed when result is 3.23567? It will be 3.235 or 3.236?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.