INTEGMAX - Integral Maximization

no tags 

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 ≤ 104 ).
The second line contains N different integers Xi separated by single spaces (1 ≤ Xi ≤ 104
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 ≤ 104 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: 2012-04-09 10:57:27

Last edit: 2012-04-09 11:29:15
Sushovan Sen: 2011-03-13 03:12:34

Plz explain second test case.


Added by:Pablo Ariel Heiber
Date:2010-08-19
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