What to read

flows graph optimization DAG

A contestant is preparing with this catalogue. Each problem solved earns points, but a problem can be solved only after reading all the articles it belongs to, and an article can be read only after reading its prerequisites. Reading takes time, and a minute of reading costs a point. What should be read and what solved so that the difference “points minus minutes” is greatest?

In general form: there are n tasks, each with a value v, positive (a problem) or negative (an article that takes time). Some tasks require others: a can be taken on only if b is taken on too. Requirements may form cycles; then such tasks are taken together or not at all. Choose a set of tasks that, together with each task, contains everything it requires, with the greatest sum of values. The empty set is allowed.

Tests 3 and 4 are the catalogue itself as of 17 October 2026: 155 articles with their reading time and prerequisites and 286 problems, each unit of a problem’s difficulty earning 10 points in the third test and 15 in the fourth.

Input

The first line holds n and m (1 ≤ n ≤ 2000, 0 ≤ m ≤ 20,000). The second holds n values v₁, …, v_n (|v_i| ≤ 10⁹). Then m lines a b (1 ≤ a, b ≤ n, a ≠ b): task a requires task b.

Output

The greatest sum of values of an allowed set.

Examples

Example 1

Input

Output

Example 2

Input

Output

Limits

Time · Python: 8000 ms
Time · Go: 1500 ms
Memory: 256 MB
Judging: 10 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Check the first example: neither problem on its own pays for the article, but the two together do. Can problems be decided “one by one”?

2Hint 2

Picture the choice as a cut: the source means “take”, the sink “do not take”. Which edges should fall in the cut if a problem was not taken? If an article was taken? And what should be done with the requirement “no a without b” so that a cut violating it becomes unacceptably expensive?

3The idea

This is the maximum-weight closure problem, and it reduces to a minimum cut. From the source to each task with v > 0 lead an edge of price v, from each task with v < 0 to the sink one of price −v, and for each requirement “a requires b” an edge a → b of infinite price. The answer is the sum of the positive values minus the value of the maximum flow.

4Walkthrough

Let S be the side of the cut with the source, and the set of tasks the vertices of S. The cut is finite if and only if no infinite edge a → b leads out of S, that is, the set contains, together with each task, everything it requires. The price of such a cut is made of two parts: the edges source → v for positive tasks not taken (points missed) and the edges v → sink for negative tasks taken (minutes spent). So the price of the cut = (the sum of all positive values) − (the sum of the values of the set). The minimum cut gives the greatest sum of the set, and its price is found by a maximum flow, here Dinic’s algorithm.

Cycles in the requirements get in the way of nothing: infinite edges in both directions simply prevent the cycle from being cut.

On the catalogue, with 10 points per unit of difficulty, the answer is 3554. A greedy “problem by problem” choice, which takes a problem only if it alone pays for everything missing, gets 82: the catalogue’s articles share many prerequisites, and they pay off only together.

4+Solution

5Complexity

There are n + 2 vertices and at most n + m edges. Dinic’s algorithm is O(V² E) in the worst case, much faster on such graphs. Long chains of requirements are a bad case for Dinic: each phase lengthens the path by one edge, so in the tests chains are at most 600 long.

6Common mistakes

Problems one at a time. Deciding whether to take a problem by looking only at it is wrong.py. It does not see that two problems together pay for a shared article that neither pays for alone.
A finite “infinity”. If an infinite edge is cheaper than the sum of all values, the cut may prefer it, and a requirement is violated. Values reach 10⁹ and their sum 2·10¹²: “infinity” has to be larger.
A 32-bit sum. In the seventh test the answer does not fit in 32 bits.

Algorithms behind it

GRA Algorithm Minimum cut The cheapest border in a graph: it cuts an object out of a photo and finds the weak spot of a network. O(m n² |C|) 2 problems GRA Algorithm Maximum flow The largest flow from a source to a sink and the bottleneck of the network: Ford–Fulkerson, Edmonds–Karp, the cut theorem. O(V E²) 2 problems