P12229 「WyOJ Round 1」归 · 星穗垂野

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

给定长度为 $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}

**本题有多组数据**。 第一行一个整数 $T$，表示数据组数。 对于每组数据： 第一行两个整数 $n,C$。 第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。 第三行 $n$ 个整数，第 $i$ 个整数表示 $b_i$。

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

对于 $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$ | $5$ | $n\le 300$ | | $5$ | $5$ | $n\le 1000$ | | $6\sim 10$ | $5$ | $n\le 10^5$ |