题目背景

神龟虽寿，犹有竟时；腾蛇乘雾，终为土灰。老骥伏枥，志在千里；烈士暮年，壮心不已。

——曹操《龟虽寿》

题目描述

给定长度为 $n$ 的序列 $(a_1,a_2,\dots,a_n)$，定义函数 $w(l,r)$ 为：

$$w(l,r)= \gcd(a_l,a_{l+1},\dots,a_{r})\times \sum_{i=l}^r b_i $$

定义序列选择互不相交的 $m$ 段（$m>0$）区间 $[l_1,r_1],[l_2,r_2],\dots,[l_{m},r_{m}]$（即 $\forall i\in [1,m), r_{i}<l_{i+1}$）的代价为：

$$\sum_{i=1}^{m} w(l_{i},r_{i})$$

定义好的选择为 $\forall i\in [1,m], r_{i}-l_{i}+1\ge \gcd(a_{l_i},a_{l_i+1},\dots,a_{r_i})\ge r_{i-1}-l_{i-1}+1$。其中，$l_0=r_0=0$。

选择 $m$ 段的额外代价是 $mC$，其中 $C$ 为给定的常数。

试求 $a$ 序列的好的选择的最小代价。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个整数 $n,C$。

第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

第三行 $n$ 个整数，第 $i$ 个整数表示 $b_i$。

输出格式

一行一个整数，表示最小代价。

1
6 -7
1 1 4 5 1 4
1 9 1 9 8 10

-6

提示

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le a_i\le 10^5$，$0\le b_i\le 10^5$，$-10^9\le C\le 10^9$。保证至少能够选择一段。

测试点	$T$	特殊性质
$1$	$10^3$	$n\le 10$
$2$	$5$	$C\ge 0$
$3,4$		$n\le 300$
$5$		$n\le 1000$
$6\sim 10$		$n\le 10^5$