Minimizing Good Selection Cost

Given two sequences of length n: a and b, we define a function

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

A selection consists of m > 0 non-overlapping intervals \([l_1,r_1], [l_2,r_2], \dots, [l_m,r_m]\) (i.e. for all i\in[1,m), r_i < l_{i+1}), and its cost is defined as:

$$\sum_{i=1}^{m}w(l_i,r_i) + mC$$

Furthermore, a selection is called good if for every interval \([l_i,r_i]\) the following conditions hold:

$$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 $$

with the convention \(l_0=r_0=0\). Your task is to compute the minimum cost among all good selections.

inputFormat

The first line contains two integers n and C (1 \le n \le 100, constraints are small).

The second line contains n integers denoting the array a.

The third line contains n integers denoting the array b.

outputFormat

Output the minimum cost among all good selections.

sample

3 10
2 2 3
1 2 3

43

</p>