INTEGMAX  Integral Maximization
A set of points on the XY plane, all of them with different x coordinate, defines a polygonal
line in the following way: sort the points in increasing order of their x coordinates, and connect
each point with its neighbors. The integral of such polygonal line is the area contained below
the line and above the x axis, between the first and last values of x. For instance, the set of
points {(5, 1), (3, 2), (6, 2), (2, 1)} defines the polygonal line shown in the figure; the integral of
the polygonal line is the shaded area, with a value of 6.
Given a set of N different values for x, and a set of N values for y, we want to pair them to
form N points on the plane such that the integral of the polygonal line defined by the points is
as large as possible.
Input
The input contains several test cases, each one described in exactly three lines. The first line of
each test case contains an integer N indicating the number of points in the set (2 ≤ N ≤ 10^{4} ).
The second line contains N different integers Xi separated by single spaces (1 ≤ Xi ≤ 10^{4}
for 1 ≤ i ≤ N ); these integers represent the values of x and are given in increasing order
(Xi < Xi+1 for 1 ≤ i ≤ N − 1). The third line contains N integers Yi separated by single spaces
(1 ≤ Yi ≤ 10^{4} for 1 ≤ i ≤ N ); these integers represent the values of y and are not given in any
particular order. The last line of the input contains a single −1 and should not be processed
as a test case.
Output
For each test case output a single line with the maximum integral of a polygonal line formed
by pairing the input values, using exactly one decimal digit. Notice that one decimal digit is
always enough to represent the exact value of the integral of a polygonal line defined by points
with integer coordinates.
Example
Input:
2
1 2
1 2
4
2 3 5 6
1 2 1 2
1
Output: 1.5
7.0
hide comments
nani:
20120409 10:57:27
Last edit: 20120409 11:29:15 

Sushovan Sen:
20110313 03:12:34
Plz explain second test case. 
Added by:  Pablo Ariel Heiber 
Date:  20100819 
Time limit:  0.393s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 VB.NET 
Resource:  FCEyN UBA ICPC Selection 2008 