Tarjan求强连通分量，RE on #6,#7,#9,#10 https://www.luogu.com.cn/record/194428602

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e4 + 10;
const int M = 5 * 1e3 + 10;

int n, m;
vector<int> e[N];
vector<pair<int, int> > scc;
int f[M];
int cost[N];
int earn[N];
int dfn[N];
bool ins[N];
int low[N];
stack<int> st;
int idx;
int money;

void dfs(int u) {
	dfn[u] = low[u] = ++idx;
	ins[u] = 1;
	st.push(u);
	for (auto v : e[u]) {
		if (!dfn[v]) {
			dfs(v);
			low[u] = min(low[u], low[v]);
		}
		else {
			if (ins[v])
				low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		int a, b;
		a = b = 0;
		while (1) {
			int j = st.top();
			a += cost[j];
			b += earn[j];
			ins[j] = 0;
			st.pop();
			if (j == u) break;
		}
		scc.push_back({a, b});
	}
}

signed main() {
	cin >> n >> m >> money;
	for (int i = 1; i <= n; ++i) {
		cin >> cost[i] >> earn[i];
	}
	for (int i = 1; i <= m; ++i) {
		int u, v;
		cin >> u >> v;
		if (u == v);
		else
			e[u].push_back(v), e[v].push_back(u);
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfn[i]) {
			dfs(i);
		}
	}
	// cout<<"----------------------------\n";
	// cout<<scc.size()<<"\n";
	// for(auto j:scc){
	// 	cout<<j.first<<" "<<j.second<<"\n";
	// }
	// cout<<"---------------------------\n";
	for (int i = 1; i <= (int)scc.size(); ++i) {
		for (int j = money; j >= scc[i - 1].first; --j) {
			int a = scc[i - 1].first;
			int b = scc[i - 1].second;
			f[j] = max(f[j], f[j - a] + b);
		}
	}
	cout << f[money] << "\n";
	return 0;
}