题目背景

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

——曹操《龟虽寿》

题目描述

给定长度为 $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}]$（即对于任意 $i \in [1, m), r_i \lt 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

输入 #1

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

输出 #1

-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$。保证至少能够选择一段。

\begin{array}{|c|c|c|} \hline \textbf{测试点} & T & \textbf{特殊性质} \\ \hline 1 & 10^3 & n\le 10 \\ \hline 2 & 5 & C\ge 0 \\ \hline 3,4 & 5 & n\le 300 \\ \hline 5 & 5 & n\le 1000 \\ \hline 6\sim 10 & 5 & n\le 10^5 \\ \hline \end{array}