Problem: Problem

Lahuy had no time off and was free, and somehow wanted to eat donuts, so he decided to go around the store and buy donuts.
There is one donut shop in each city, and all donut shops are closed on odd days.
Lahuy has a taste for donuts, so the degree of satisfaction you get depends on the store.
So Lahuy decided to get as much satisfaction as possible by acting optimally.


In the world where Lahuy lives, there are n cities, each assigned a number from 0 to n-1, which are connected by m roads.
Each road is a one-way street, and Lahuy can move from town ai to town bi.
At first Lahuy is in town 0 on even days.
Lahuy does not stay in the city, but crosses one road a day and moves to another city.
On the day Lahuy arrives in town i, if the store is open, buy one donut and get satisfaction ci.
You can visit the same city as many times as you like, but only buy once at a store.
Find the maximum total satisfaction when you act optimally until Lahuy is no longer satisfied.

Constraints

The input satisfies the following conditions.

* 1 ≤ n ≤ 105
* 0 ≤ m ≤ min (n × (n−1), 105)
* 0 ≤ ci ≤ 1000
* 0 ≤ ai, bi ≤ n − 1
* Self-loop, no multiple edges

Input


n m
c0 ... cn−1
a0 b0
...
am−1 bm−1


All inputs are given as integers.
The number n of towns and the number m of roads are given on the first line, separated by blanks.
On the second line, the satisfaction ci obtained when purchasing donuts at the store in town i is given separated by blanks.
The following m lines are given ai and bi, which represent road information, separated by blanks.

Output

Output the maximum value of total satisfaction on one line.

Examples

Input

2 1
1 2
0 1


Output

1


Input

5 5
1 1 1 1 1
0 1
1 2
2 3
3 0
3 4


Output

3


Input

4 4
1 1 1 1
0 1
1 2
2 0
2 3


Output

4

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
struct Dscc {
public:

	//fst:belongs , scd:newedges
	pair<vector<vector<int>>, vector<vector<int>>>get(const vector<vector<int>>&edges) {
		nums.resize(edges.size());
		fill(nums.begin(), nums.end(), -1);
		vector<vector<int>>revedges(edges.size());
		for (int i = 0; i < edges.size(); ++i) {
			for (auto j : edges[i]) {
				revedges[j].push_back(i);
			}
		}
		int num = 0;
		for (int i = 0; i < edges.size(); ++i) {
			dfs(i, num, edges);
		}
		vector<int>big(nums.size());
		for (int i = 0; i < nums.size(); ++i) {
			big[nums[i]] = i;
		}
		reverse(big.begin(), big.end());
		unis.resize(edges.size());
		fill(unis.begin(), unis.end(), -1);
		num = 0;
		for (int i = 0; i < big.size(); ++i) {

			dfs2(big[i], num, revedges);
			num++;
		}
		vector<int>nums;
		for (int i = 0; i < unis.size(); ++i) {
			nums.push_back(unis[i]);
		}
		sort(nums.begin(), nums.end());
		nums.erase(unique(nums.begin(), nums.end()), nums.end());


		map<int, int>mp;
		for (int i = 0; i < nums.size(); ++i) {
			mp[nums[i]] = i;
		}
		for (int i = 0; i < unis.size(); ++i) {
			unis[i] = mp[unis[i]];
		}

		vector<vector<int>>belongs(nums.size());
		for (int i = 0; i < unis.size(); ++i) {
			belongs[unis[i]].push_back(i);
		}
		vector<vector<int>>newedges(nums.size());
		for (int i = 0; i < edges.size(); ++i) {
			for (auto j : edges[i]) {
				if (unis[i] != unis[j]) {
					newedges[unis[i]].push_back(unis[j]);
				}
			}
		}
		return make_pair(belongs, newedges);
	}
public:
	vector<int>nums;
	vector<int>unis;


	void dfs(const int id, int &num, const vector<vector<int>>&edges) {
		if (nums[id] != -1)return;
		else {
			nums[id] = -2;
			for (auto i : edges[id]) {
				dfs(i, num, edges);
			}
		}
		nums[id] = num++;
		return;
	}
	void dfs2(const int id, const int &num, const vector<vector<int>>&edges) {
		if (unis[id] != -1)return;
		else {
			unis[id] = -2;
			for (auto i : edges[id])
				dfs2(i, num, edges);
		}
		unis[id] = num;
		return;
	}

}dscc;

void dfs(const int now, const vector<vector<int>>&edges, vector<int>&colors,int num) {
	colors[now]=num;
	for (auto e : edges[now]) {
		if(dscc.unis[now]!=dscc.unis[e])continue;
		else {
			if (num != 2) {
				if (colors[e] == num) {
					dfs(e, edges, colors, 2);
					
				}
				else if (colors[e] + num == 1) {

				}
				else if(colors[e]!=2){
					dfs(e,edges,colors,!num);
				}
			}
			else {
				if (colors[e] == 2) {

				}
				else {
					dfs(e,edges,colors,2);
				}
			}
			
		}
	}
}

void cango(const int now, const vector<vector<int>>&edges,vector<int>&can) {
	can[now]=true;
	for (auto e : edges[now]) {
		if(!can[e])cango(e,edges,can);
	}
}
int main() {
	int N,M;
	vector<int>cs;
	cin >> N >> M;
	vector<vector<int>>edges(N);
	{
		for (int i = 0; i < N; ++i) {
			int a; cin >> a;
			cs.push_back(a);
		}
		for (int i = 0; i < M; ++i) {
			int a, b; cin >> a >> b;
			edges[a].push_back(b);
		}
		vector<int>can(N);
		cango(0, edges, can);
		map<int,int>mp;
		int id=0;
		vector<int>ncs;
		for (int i = 0; i < N; ++i) {
			if (can[i]) {
				mp[i] = id++;
				ncs.push_back(cs[i]);
			}
		}
		vector<vector<int>>nedges(ncs.size());
		for (int i = 0; i < N; ++i) {
			if (can[i]) {
				for (int j = 0; j < edges[i].size(); ++j) {
					if (can[i] && can[edges[i][j]]) {
						nedges[mp[i]].push_back(mp[edges[i][j]]);
					}
				}
			}
		}
		cs=ncs;
		edges=nedges;
		N=cs.size();
	}
	
	auto p=dscc.get(edges);
	vector<int>colors(N,-1);
	for (int i = 0; i < N; ++i) {
		if (colors[i] == -1) {

			dfs(i, edges, colors, 0);
		}
	}

	vector<vector<pair<int,bool>>>nextedges(p.second.size());
	vector<vector<int>>sums(p.second.size(),vector<int>(2));
	vector<int>comes(p.second.size());
	vector<int>biparates(p.second.size());
	for (int i = 0; i < N; ++i) {
		if (colors[i] == 2) {
			sums[dscc.unis[i]][0]+=cs[i];
			biparates[dscc.unis[i]]=false;
		}
		else {
			biparates[dscc.unis[i]]=true;
			sums[dscc.unis[i]][colors[i]]+=cs[i];
			
		}
		for (auto e : edges[i]) {
			if (dscc.unis[i] != dscc.unis[e]) {
				const int from=dscc.unis[i];
				const int to=dscc.unis[e];
				if (colors[i] == 2 || colors[e] == 2) {
					nextedges[from].push_back(make_pair(to,true));
				}
				else {
					nextedges[from].push_back(make_pair(to,colors[i]==colors[e]));
				}
				comes[to]--;
			}
		}
	}
	queue<int>que;
	vector<vector<int>>memo(p.second.size(),vector<int>(2,-1e9));


	memo[0][0]=sums[0][0];
	que.push(0);
		
	
	while (!que.empty()) {
		const int now=que.front();
		que.pop();
		for (auto e : nextedges[now]) {
			const int next=e.first;
			comes[next]++;
			if(!comes[next])que.push(next);
			if (!biparates[next]) {
				const int nextcost=max(memo[now][0],memo[now][1])+sums[next][0];
				if (nextcost > memo[next][0]) {
					memo[next][0]=nextcost;
				}
			}
			else if(!biparates[now]){
				for (int i = 0; i < 2; ++i) {
					const int nextcost=memo[now][0]+sums[next][i];
					if (nextcost > memo[next][i]) {
						memo[next][i]=nextcost;
					}
				}
			}
			else {
				for (int i = 0; i < 2; ++i) {
					if (!e.second) {
						const int nextcost = memo[now][i] + sums[next][i];
						if (nextcost > memo[next][i]) {
							memo[next][i] = nextcost;
						}
					}
					else {
						const int nextcost=memo[now][i]+sums[next][!i];
						if (nextcost > memo[next][!i]) {
							memo[next][!i]=nextcost;
						}
					}
				}
			}
		}
	}
	int ans=0;
	for (int i = 0; i < memo.size(); ++i) {
		for (int j = 0; j < 2; ++j) {
			ans=max(ans,memo[i][j]);
		}
	}
	cout<<ans<<endl;
	return 0;
}