这题用dfs其实更好理解： 核心idea就是找一个组合，他们的gcd为1。

由于需要排序的数量不大，就300左右，其实把cost进行排序然后剪枝应该更快一些的 注意dfs时不要忘了一开始的for循环，我就是上来写的dfs只从0开始一直不过，才忘记自己没有设置根结点，需要手动遍历最开始的一层（如果序号从1开始，0为根结点就从0开始，修改下代码且不用手动for循环了）

然后一开始一直卡时间，看了别人的题解才发现漏了两个剪枝：

一个组合产生的gcd，如果其它组合的cost更小，就不需要这个组合了，剪掉-usedmap；一个组合产生的cost，如果其它组合的gcd更小，也不需要这个组合了，剪掉-costmap！

当然因为已经排好序了，如果一个组合的cost已经大于获得gcd=1的cost了，自然也不需要关心了，剪掉；另外如果已经获得gcd=1的情况，也不需要继续遍历下去了，剪掉。这两个剪枝应该是比较简单的。

// c++
#include<iostream>
#include<algorithm>
#include<climits>
#include<cstring>
#include<map>
#include<unordered_map>
#include<bitset>
#include<unordered_set>
#include<set>
#include<deque>
#include<queue>
using namespace std;

long n;
long ans = LONG_MAX;
constexpr int maxn = 310;
struct thing {
    long l, c;
    bool operator<(const thing& t2)const noexcept {
        return c < t2.c;
    }
}things[maxn];
unordered_map<long, long>usedmap, costmap;

inline void read(long& res)
{
    char c;
    long flag = 1;
    while ((c = getchar()) < '0' || c > '9')if (c == '-')flag = -1;res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')res = res * 10 + c - '0';res *= flag;
}

inline int gcd(long a, long b) {
    long tp;
    while (1) {
        tp = a % b;
        if (tp == 0)break;
        else a = b, b = tp;
    }
    return b;
}

inline void dfs(int ind, long cost, long maxgcd) {
    if (cost >= ans)return;

    auto it = usedmap.find(maxgcd);
    if (it == usedmap.end())usedmap[maxgcd] = cost;
    else {
        if (it->second <= cost)return;
    }
    it = costmap.find(cost);
    if (it == costmap.end())costmap[cost] = maxgcd;
    else {
        if (it->second <= maxgcd)return;
    }

    if (maxgcd == 1) {
        ans = min(ans, cost);
        return;
    }
    else {
        for (int i = ind + 1;i < n;i++) {
            dfs(i, cost + things[i].c, gcd(maxgcd, things[i].l));
        }
    }
}

int main(int argc, char const* argv[])
{
    read(n);
    long tl, tc;
    for (int i = 0; i < n; i++)
    {
        read(tl);
        things[i].l = tl;
    }
    for (int i = 0; i < n; i++)
    {
        read(tc);
        things[i].c = tc;
    }
    sort(things, things + n);
    // for (int i = 0;i < n;i++)cout << "things[" << i << "]=" << things[i].l << " " << things[i].c << endl;
    for (int i = 0;i < n;i++)dfs(i, things[i].c, things[i].l);
    cout << (ans == LONG_MAX ? -1l : ans) << endl;
    return 0;
}