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

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

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

特别的，若 i 大于 m，那么加速参考 b_m，即速度至少增加 2 倍、至多增加 b_m 倍。如 加速参数只有两条 b_1，b_2，则第三秒时加速参考 b_2。增加的速度必须为原本速度的整数倍。

飞船改变速度后的 1 秒内，飞船都会按此速度飞行。

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

输入共四行。

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

第二行 m 个整数 b_1、b_2、\dots、b_m，代表飞船的发动机参数序列。

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

第四行 n 个整数 c_1、c_2、\dots、c_n，代表起点正前方空间站的距离。

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

数据范围

对于 30\% 的数据，保证输入的 \max\{c_1,c_2,\dots,c_n\} \leq 30；其中数据 1，m=n=1。

对于 70\% 的数据，保证输入的 \max\{c_1,c_2,\dots,c_n\} \leq 100000。

对于 100\% 的数据，保证输入的 \max\{c_1,c_2,\dots,c_n\} \leq 10^9，n,m,\max\{b_1,b_2, \dots ,b_n\} \leq 20。

样例解释 1

初始速度为 1 km/s，0 \dots 1 s 走了 1 km。1 s 时将速度调整 2 倍为 2 km/s，1 \sim 2 s 走了 2 km。2 s时将速度调整 4 倍为 8 km/s，2\sim 3s 走了 8 km。3s 时将速度调整 7 倍为 56km/s，3 \sim 4s 走了 56km。

4s 时将速度调整 9 倍为 504 km/s，4 \sim 5s 走了 504km。

5s 一共走了 1+2+8+56+504=571 km。

BCSP-X小高组编程能力样卷-T4

BCSP-X