510D - Fox And Jumping - CodeForces Solution

#define fst std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout << std::fixed << std::setprecision(20)
#define le "\n"
#define ll long long 
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+50;
const int mod=998244353;
map<ll,ll> mp;

ll gcd(ll n,ll m){
    return m? gcd(m,n%m): n;
}

int main() {
    int n; cin>>n;
    vector<ll> a(n+1),w(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>w[i];

    for(int i=1;i<=n;i++){
        mp[a[i]] = mp[a[i]] ? min(mp[a[i]],w[i]) : w[i]; 
        for(auto j: mp){
            mp[gcd(j.first,a[i])] = mp[gcd(j.first,a[i])] ? min(mp[gcd(j.first,a[i])],j.second+w[i]) : j.second+w[i];
        }
    }
    cout<<(mp[1] ? mp[1]:-1)<<le;
    return 0;
}