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 ≤ 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

Added by:Pablo Ariel Heiber
Date:2010-08-19
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 VB.NET
Resource:FCEyN UBA ICPC Selection 2008

hide comments
2011-03-13 03:12:34 Sushovan Sen
Plz explain second test case.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.