Donuts Purchase

Time Limit : 2 sec, Memory Limit : 262142 KB

Problem K: Donuts Purchase

Problem

ラフイは休暇の間することがなく暇で、なんとなくドーナツが食べたくなったので、店を巡りドーナツを購入していくことにした。
各街には1軒のドーナツ店があり、すべてのドーナツ店は奇数日が定休日となっている。
ラフイにはドーナツの好みがあるので、店によって得られる満足度が違う。
そこでラフイは最適に行動することで、できるだけ多くの満足度を得ることにした。

ラフイが住んでいる世界には、それぞれ0からn-1の番号が割り当てられたn個の街があり、それらはm本の道で繋がれている。
それぞれの道は一方通行になっており、ラフイは街aiから街biへ移動することができる。
最初ラフイは偶数日に街0にいる。
ラフイは街には留まらずに、1日に道を1本渡り別の街に移動する。
ラフイは街iに到着した日に、店が営業していれば1つドーナツを購入し、満足度ciを得る。
同じ街は何度でも訪れることができるが、1つの店では1度しか購入しない。
ラフイがこれ以上満足度を得られない状態になるまで最適に行動した時の満足度の合計の最大を求めよ。

Input

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

入力はすべて整数で与えられる。
1行目に街の数nと道の数mが空白区切りで与えられる。
2行目に街iの店でドーナツを購入した際に得られる満足度ciが空白区切りで与えられる。
続くm行に道の情報を表すaibiが空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

  • 1 ≤ n ≤ 105
  • 0 ≤ m ≤ min(n×(n−1),105)
  • 0 ≤ ci ≤ 1000
  • 0 ≤ ai,bin − 1
  • 自己ループ、多重辺は存在しない

Output

満足度の合計の最大値を1行に出力せよ。

Sample Input 1

2 1
1 2
0 1

Sample Output 1

1

Sample Input 2

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

Sample Output 2

3

Sample Input 3

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

Sample Output 3

4

Source: Ritsumeikan University Programming Camp 2017 , Day 2, Shiga, Japan, 2017-03-23