题目描述

为了快速在宇宙中穿梭，人类研发了一款能够瞬间加速的宇宙飞船。

这款飞船起步时可以任意选择速度 a 千米每秒，a 必须为正整数。

另外此飞船的发动机有一个长度为 m 的加速参数序列 b1、b2、...、bm，起步后第 i 秒可以根据发动机参数 bi 来调整飞船速度，使其至少增加 2 倍、至多增加 bi 倍；如 bi=3，则可以选择加速 2 倍或 3 倍。

特别的，若 i 大于 m，那么加速参考 bm，即速度至少增加 2 倍、至多增加 bm 倍。如加速参数只有两条 b1，b2，则第三秒时加速参考 b2。增加的速度必须为原本速度的整数倍。飞船改变速度后的 1 秒内，飞船都会按此速度飞行。

你是其中一艘宇宙飞船的驾驶员，现在你需要执行飞行任务，经过 n 个排成一条直线的空间站，第 i 个空间站在起点前方距离 ci 千米。如果飞船正好在整数秒抵达空间站，那么这个空间站的信息可以被飞船获得。你需要计算在获得所有空间站信息的基础上，飞行时间如何尽可能的短，输出这个最短飞行时间秒数。如果不能获取所有空间站信息，请输出-1.

输入格式

共四行

第一行一个整数 m，代表飞船的发动机参数序列长度；

第二行 m 个整数 b1、b2、...、bm，代表飞船的发动机参数序列；

第三行一个整数 n，代表空间站数量；

第四行 n 个整数 c1、c2、...、cn，代表起点正前方空间站的距离。

输出格式

仅一个正整数，代表最短飞行时间秒数或者-1。

样例

2 
9 9 
1 
571

5

样例解释

初始速度为 1km/s,0-1s 走了 1km；1s 时将速度调整 2 倍为 2km/s，1-2s 走了 2km；2s时将速度调整 4 倍为 8km/s，2-3s 走了 8km；3s 时将速度调整 7 倍为 56km/s，3-4s 走了 56km；4s 时将速度调整 9 倍为 504km/s，4-5s 走了 504km。5s 一共走了 1+2+8+56+504=571km。

数据范围

对于 30%的数据，保证输入的 max{c1、c2、...、cn}<=30；其中数据 1，m=n=1；

对于 70%的数据，保证输入的 max{c1、c2、...、cn}<=100000；

对于 100%的数据，保证输入的 max{c1、c2、...、cn}<=10^9，n,m,max{b1、b2、...、bn}<=20。