3979. 篮球

【题目背景】

最近一个月各个学校应该都举办球类运动会了吧。

$\text{curry}$ 大神在班赛中空砍 $26$ 分，奈何队友不给力，遗憾败北，还被对手嘲讽道：“菜就多练，输不起就别怪队友！”

【题目描述】

好胜心极强的 $\text{curry}$ 准备参加学校的篮球队选拔，努力练习篮球。选拔规则是这样的：球场中间有 $n$ 个防守人排成一列，每个防守人有一个能力值 $b_i$，刚开始 $\text{curry}$ 在第 $1$ 名防守人的前面，他需要连续运球过掉这 $n$ 名防守人到达球场对面，他可以自己选择左边或者右边过人，但是不能连续 $3$ 次选择同一个方向，时间越快越好。正常运球从左边过掉第 $i$ 名防守人需要 $l_i$ 秒的时间，从右边过掉第 $i$ 名防守人需要 $r_i$ 秒的时间。

但是由于班赛的失利激起了他求胜的欲望，所以他有一个大招。他会在比赛前选出 $m$ 个正整数 $a_1,a_2,...,a_m$，如果当前他处于第 $s$ 名防守人身前，且存在一对 $a_i,a_j$ 满足 $\gcd(a_i,a_j)=b_s$ 且 $i\ne j$，那么他可以选择直接跳过这名防守人来到下一个防守人（第 $s+1$ 个）面前，即消耗时间为 $0$。当然他也可以选择不使用大招。特别地，如果 $s=n$ 且可以使用大招时他将会直接完成测试。大招释放后将会重新计数连续 $3$ 次的是否选择同一方向的规则。

求 $\text{curry}$ 完成选拔测试所需要的最少时间。

说明：$\gcd(a,b)$ 表示整数 $a,b$ 的最大公约数。

【输入格式】

输入包含 $5$ 行。

第一行包含 $2$ 个正整数 $n,m$。

第二行共 $m$ 个整数 $a_1,a_2,a_3,...,a_{m-1},a_m$ ，表示刚开始指定的数值。

第三行共 $n$ 个整数 $b_1,b_2,b_3,...,b_{n-1},b_n$ ，表示防守人的能力值。

第四行共 $n$ 个整数 $l_1,l_2,l_3,...,l_{n-1},l_n$ ，如题意。

第五行共 $n$ 个整数 $r_1,r_2,r_3,...,r_{n-1},r_n$ ，如题意。

每一行内的数字之间用空格隔开。

【输出格式】

输出一行一个整数表示最少时间。

【样例1输入】

3 5
2 4 3 6 9
7 5 4
3 1 2
4 3 7

【样例1输出】

7

【样例1说明】

不使用大招，方向分别为右，左，左，$4+1+2=7$。

【样例2输入】

4 6
12 18 5 9 3 10
7 2 5 6
3 5 2 4
1 4 6 2

【样例2输出】

1

【数据规模与约定】

对于 $15\%$ 的数据，满足 $1\le n\le 15$.

对于 $30\%$ 的数据，满足 $1\le n\le 100,1\le m\le 100,1\le a_i,b_i\le 10^9$。

对于 $50\%$ 的数据，满足 $1\le n\le 800,1\le m\le 300$。

对于 $60\%$ 的数据，满足 $1\le n\le 1000,1\le m\le 500$。

对于 $100\%$ 的数据，保证 $1\le n\le 2\times 10^3,1\le m\le 10^3,1\le a_i,b_i\le 10^{15},1\le l_i,r_i\le 10^9$。

【来源】

2024年校际联合邀请赛 普及组-第1场 Task4