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.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        try (Scanner in = new Scanner(System.in)) {
            int N = in.nextInt();

            int[] t = new int[N];
            for (int i = 0; i < N; i++) {
                t[i] = in.nextInt();
            }

            int[] v = new int[N];
            for (int i = 0; i < N; i++) {
                v[i] = in.nextInt();
            }

            int sumTime = 0;
            for (int i = 0; i < N; i++) {
                sumTime += t[i];
            }

            // max speed of segment
            int[] maxSpeed = new int[sumTime];
            // Arrays.fill(maxSpeed, (int) 1e9);
            for (int i = 0, si = 0; i < N; i++) {
                for (int j = 0; j < t[i]; j++) {
                    maxSpeed[si] = v[i];
                    // speed[si] = v[i];
                    si++;
                }
            }
            // speed at the point
            int[] speed = new int[sumTime + 1];
            // for (int i = 0, si = 0; i < N; i++) {
            // for (int j = 0; j < t[i]; j++) {
            // maxSpeed[si] = v[i];
            // speed[si] = v[i];
            // si++;
            // }
            // }
            for (int i = 0; i < speed.length; i++) {
                speed[i] = i == speed.length - 1 ? maxSpeed[i - 1] : i == 0 ? maxSpeed[i] : Math.min(maxSpeed[i - 1], maxSpeed[i]);
            }

            // for (int i = 0, si = 0; i + 1 < maxSpeed.length; i++) {
            // // for (int j = 0; j < t[i]; j++) {
            // // if (si - 1 >= 0) {
            // // maxSpeed[si] = Math.min(maxSpeed[si], maxSpeed[si - 1]);
            // // }
            // maxSpeed[si] = Math.min(maxSpeed[si], maxSpeed[si + 1]);
            // speed[si++] = maxSpeed[si];
            // // }
            // }

            // for (int i = 0, si = 0; i + 1 < maxSpeed.length; i++) {
            // // for (int j = 0; j < t[i]; j++) {
            // if (si - 1 >= 0) {
            // maxSpeed[si] = Math.min(maxSpeed[si], maxSpeed[si - 1]);
            // speed[si] = Math.min(speed[si], speed[si - 1]);
            // }
            // maxSpeed[si] = Math.min(maxSpeed[si], maxSpeed[si + 1]);
            // speed[si] = Math.min(speed[si], speed[si + 1]);
            // // speed[si++] = maxSpeed[si];
            // // }
            // si++;
            // }

            speed[0] = 0;
            speed[speed.length - 1] = 0;

            for (;;) {
                boolean update = false;
                for (int i = 0; i + 1 < speed.length; i++) {
                    if (speed[i + 1] > speed[i] + 1) {
                        speed[i + 1] = speed[i] + 1;
                        update = true;
                    }
                }
                for (int i = speed.length - 1; i - 1 >= 0; i--) {
                    if (speed[i - 1] > speed[i] + 1) {
                        speed[i - 1] = speed[i] + 1;
                        update = true;
                    }
                }
                if (!update) {
                    break;
                }
            }

            // for (int i = 0, si = 0; i + 1 < maxSpeed.length; i++) {
            // // for (int j = 0; j < t[i]; j++) {
            // // if (si - 1 >= 0) {
            // // maxSpeed[si] = Math.min(maxSpeed[si], maxSpeed[si - 1]);
            // // speed[si] = Math.min(speed[si], speed[si - 1]);
            // // }
            // maxSpeed[si] = Math.min(maxSpeed[si], maxSpeed[si + 1]);
            // speed[si] = Math.min(speed[si], speed[si + 1]);
            // // speed[si++] = maxSpeed[si];
            // // }
            // si++;
            // }

            for (int i = 0; i < speed.length; i += 10) {
                Utils.debug(Arrays.copyOfRange(speed, i, i + 10));
            }

            double sum = 0;
            for (int i = 0; i + 1 < speed.length; i++) {
                sum += (speed[i + 1] + speed[i]) / 2.0;
                if (speed[i + 1] == speed[i] && speed[i] != maxSpeed[i]) {
                    sum += 0.25;
                }
                Utils.debug(i, sum, speed[i + 1], speed[i]);
            }

            System.out.println(sum);

        }
    }

}

final class Utils {
    private Utils() {
    }

    public static final void debug(Object... o) {
        System.err.println(toString(o));
    }

    public static final String toString(Object... o) {
        return Arrays.deepToString(o);
    }

}