TOI15: Budget

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const int N = 3e3 + 10;
const int P = 3e5 + 10;
using pl = pair <lli, lli>;
using pll = pair <lli, pl>;
vector <pll> path;
pl pack[P];
lli parent[N];

lli root(lli u){
    if(u == parent[u]) return u;
    return parent[u] = root(parent[u]);
}

void mrg(lli u, lli v){
    u = root(u);
    v = root(v);
    if(u == v) return;
    parent[v] = u;
}

int main(){

    lli nnode, m;
    scanf("%lld%lld", &nnode, &m);

    for(lli i=0;i<nnode;i++) parent[i] = i;

    for(lli i=1;i<=m;i++){
        lli u, v, w, state;
        scanf("%lld%lld%lld%lld", &u, &v, &w, &state);
        if(state == 0) path.push_back({w, {u, v}});
        else mrg(u, v);
    }

    lli npack;
    scanf("%lld", &npack);
    for(lli i=1;i<=npack;i++){
        lli l, p;
        scanf("%lld%lld", &l, &p);
        pack[i] = {l, p};
    }

    sort(pack + 1, pack + npack + 1);
    for(lli i=npack-1;i>=1;i--){
        pack[i].second = min(pack[i].second, pack[i+1].second);
    }

    lli len_path = path.size();
    for(lli i=0;i<len_path;i++){
        lli l = 1, r = npack, mn = npack;
        while(l <= r){
            lli mid = (l + r) / 2;
            if(pack[mid].first >= path[i].first) r = mid - 1, mn = min(mn, mid);
            else l = mid + 1;
        }
        path[i] = {pack[mn].second , {path[i].second.first, path[i].second.second}};
    }

    sort(path.begin(), path.end());

    lli ans = 0;
    for(lli i=0;i<len_path;i++){
        lli w = path[i].first;
        lli u = path[i].second.first;
        lli v = path[i].second.second;
        if(root(u) == root(v)) continue;
        mrg(u, v);
        ans += w;
    }

    printf("%lld", ans);
    return 0;
}