T4-星际穿梭

题目描述

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

这款飞船起步时可以任意选择速度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。

样例输入1

9 9
1
571

样例输出1

5

数据范围

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

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

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

样例解释1

初始速度为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。