Problem: In the year 2168, AtCoder Inc., which is much larger than now, is starting a limited express train service called AtCoder Express.

In the plan developed by the president Takahashi, the trains will run as follows:

* A train will run for (t_1 + t_2 + t_3 + ... + t_N) seconds.
* In the first t_1 seconds, a train must run at a speed of at most v_1 m/s (meters per second). Similarly, in the subsequent t_2 seconds, a train must run at a speed of at most v_2 m/s, and so on.



According to the specifications of the trains, the acceleration of a train must be always within ±1m/s^2. Additionally, a train must stop at the beginning and the end of the run.

Find the maximum possible distance that a train can cover in the run.

Constraints

* 1 \leq N \leq 100
* 1 \leq t_i \leq 200
* 1 \leq v_i \leq 100
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
t_1 t_2 t_3 … t_N
v_1 v_2 v_3 … v_N


Output

Print the maximum possible that a train can cover in the run.
Output is considered correct if its absolute difference from the judge's output is at most 10^{-3}.

Examples

Input

1
100
30


Output

2100.000000000000000


Input

2
60 50
34 38


Output

2632.000000000000000


Input

3
12 14 2
6 2 7


Output

76.000000000000000


Input

1
9
10


Output

20.250000000000000000


Input

10
64 55 27 35 76 119 7 18 49 100
29 19 31 39 27 48 41 87 55 70


Output

20291.000000000000

Solution (in JAVA):

Solution:

import java.util.Scanner;

public class Main {

	static Scanner scanner;

	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    int N=gi();
	    double[] T=new double[N];
	    double[] V=new double[N];
	    double[] V2=new double[N+1];
	    double[] V3=new double[N+1];
	    double[] vm=new double[N+1];
	    for (int i=0; i<N;i++) {
	    	T[i]=gd();
	    }
	    for (int i=0; i<N;i++) {
	    	V[i]=gd();
	    }
	    V2[0]=0;
	    V3[0]=0;
	    for (int i=1; i<N;i++) {
	    	V2[i]=Math.min(V[i-1], V[i]);
	    	V3[i]=Math.min(V[i-1], V[i]);
	    }
	    V2[N]=0;
	    V3[N]=0;

	    for (int i=1; i<N+1;i++) {
	    	if(V2[i]-V2[i-1] >T[i-1]) {
	    		V2[i]=V2[i-1]+T[i-1];
	    	} else if(V2[i-1]-V2[i] >T[i-1]) {
	    		V2[i-1]=V2[i]+T[i-1];
	    	}
	    }
	    for (int i=N-1; i>=0;i--) {
	    	if(V3[i]-V3[i+1] >T[i]) {
	    		V3[i]=V3[i+1]+T[i];
	    	} else if(V3[i+1]-V3[i] >T[i]) {
	    		V3[i+1]=V3[i]+T[i];
	    	}
	    }
	    for (int i=0; i<N+1;i++) {
	    	vm[i]=Math.min(V2[i], V3[i]);
	    }

	    double ans=0;
	    for (int i=0; i<N;i++) {
	    	if(2*V[i]-vm[i]-vm[i+1]<T[i]) {
	    		ans+=Math.pow(V[i]-vm[i], 2)/2 + Math.pow(V[i]-vm[i+1], 2)/2 + (V[i]-vm[i])*vm[i] + (V[i]-vm[i+1])*vm[i+1];
	    		ans+=(T[i] - 2*V[i]+vm[i]+vm[i+1]) * V[i];
	    	} else if(2*V[i]-vm[i]-vm[i+1]>=T[i]) {
	    		double x=(T[i]-Math.abs(vm[i+1]-vm[i]))/2;
	    		if(vm[i]>vm[i+1]) {
	    			ans+=Math.pow(x, 2)/2 + x*vm[i];
	    			ans+=Math.pow(x+vm[i]-vm[i+1], 2)/2 + vm[i+1]*(x+vm[i]-vm[i+1]);
	    		} else {
	    			ans+=Math.pow(x, 2)/2 + x*vm[i+1];
	    			ans+=Math.pow(x+vm[i+1]-vm[i], 2)/2 + vm[i]*(x+vm[i+1]-vm[i]);
	    		}
	    	}
	    }

        System.out.println(ans);
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}