ABC 257

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<tuple<ll, ll, ll>> nodes;
    rep(i, N) {
        ll x, y, P;
        cin >> x >> y >> P;
        nodes.emplace_back(x, y, P);
    }

    auto f = [&](ll x) -> bool {
        rep(s, N) {
            vector<bool> used(N);
            used[s] = true;
            queue<int> que;
            que.push(s);
            while (que.size()) {
                int now = que.front();
                que.pop();

                rep(nx, N) {
                    if (nx == now) continue;
                    if (used[nx]) continue;
                    auto [xi, yi, pi] = nodes[now];
                    auto [xj, yj, pj] = nodes[nx];
                    if (pi * x >= abs(xi - xj) + abs(yi - yj)) {
                        used[nx] = true;
                        que.push(nx);
                    }
                }
            }

            ll sum = accumulate(all(used), 0);
            if (sum == N) return true;
        }
        return false;
    };

    ll ac = 0;
    rep(i, N) rep(j, N) {
        auto [xi, yi, pi] = nodes[i];
        auto [xj, yj, pj] = nodes[j];
        chmax(ac, abs(xi - xj) + abs(yi - yj));
    }

    ll wa = -1;
    while (ac - wa > 1) {
        ll wj = (ac + wa) / 2;
        if (f(wj))
            ac = wj;
        else
            wa = wj;
    }
    cout << ac << endl;
}