题目描述

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

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

另外此飞船的发动机有一个长度为 $m$ 的加速参数序列$b_1、 b_2、...、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、 ...、 b_m$， 代表飞船的发动机参数序列；

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

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

输出格式

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

样例

2
9 9
1
571

5

样例解释 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。

数据范围

• 对于 30%的数据， 保证输入的 $max\{c_1、 c_2、 ...、 c_n\} \le 30$； 其中数据 1，$m=n=1$；
• 对于 70%的数据， 保证输入的$max\{c_1、 c_2、 ...、 c_n\} \le 100000$；
• 对于 100%的数据， 保证输入的 $max\{c_1、 c_2、 ...、 c_n\} \le 10^9， n,m,max\{b_1、 b_2、 ...、 b_n\} \le 20$。

来源

BCSP-X 2024 小学组 T4