ICAMPSEQ - IOICamp Sequence

no tags 

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

hide comments
Sahil: 2015-04-20 21:41:36

<snip>
It gives a WA

Last edit: 2023-01-18 15:14:21
Zhiang: 2013-01-20 20:08:13

Be careful!!
slow I/O routine will give TLE even if the algorithm runs in linear time

ɥsǝןǝǝu: 2012-08-05 18:45:58

i don no why i'm getting WA...

unXled: 2012-06-26 10:18:15

got AC :)
requires a fast I/O routine....

Harpreet Singh Khurana: 2012-02-10 14:08:11

can someone tell me a routine to read double in c which is faster than scanf

kipoujr: 2012-01-26 14:56:15

In order to pass, you should make your own function to read a double. Remember it can be negative too.

Krzysztof Lewko: 2011-05-31 12:54:34

Wow this problem is a pain if you have a bug in your code

SCQ: 2011-04-30 05:52:55

I keep getting TLE! Can someone help me? My solution is 16 * N

Trần Hải Ðãng: 2010-09-28 17:25:39

That 's really funny, got TLE in C++ 4.3 but AC in C++ 4.0

Pranay: 2010-09-20 18:23:40

got TLE with code in C++ 4.3 but same code in C++ 4.0 just passed!!


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