On the desert planet of Zarith, the Camlmen are responsible for harvesting elixir, a valuable substance essential for the galaxy. The harvesting and processing of elixir involves multiple stages across different processing facilities scattered throughout the vast desert. Each stage has dependencies that must be followed, where certain stages must be completed before others can begin.

While that in itself is not a big challenge, the Camlmen face threats from the harsh desert environment and the monstrous sandsnakes. Time is of the essence, and they must act fast to harvest and transport the precious elixir.

To efficiently and safely harvest the elixir, Patrick, the leader of the Camlmen, must determine the minimum time to complete all stages. Stages that do not have dependencies can be processed in parallel, but tasks that are dependent on each other must be completed in sequence.

Input

The first line contains two integers ~n~ and ~m~ ~(1 \leq n \leq 10^5, 0 \leq m \leq 2\times 10^5)~, the number of stages in the elixir processing, and the number of dependencies between processing stages.

The next ~m~ lines describe the dependencies. Each line contains two integers ~a~ and ~b~ ~(1 \leq a, b \leq n)~, indicating that stage ~a~ must be completed before stage ~b~.

The last line contains ~n~ space-separated integers, where the ~i~th integer ~t_i~ ~(1 \leq t_i \leq 10^5)~ represents the time required to complete stage ~i~.

Output

Output a single integer, the minimum time required to complete all stages, assuming an optimal path and maximising parallel processing.

Clarifications

• There are no circular dependencies.
• The stages can be processed in parallel if no dependencies exist between them.

Example

Input 1

6 6
1 2
1 3
2 4
3 4
4 5
4 6
10 5 8 7 6 4

Output 1

31

The stages and their dependencies are:

1 → 2 → 4 → 5
  ↘︎ 3 → 4 → 6

The optimal execution will be:

• Stage ~1~ finishes at time ~10~
• Stage ~2~ and ~3~ will finish at time ~15~ and ~18~ respectively
• Stage ~4~ depends on both stage ~2~ and ~3~, so it will only begin at time ~18~ and finish at time ~25~
• Stage ~5~ will finish at time ~31~
• Stage ~6~ will finish at time ~29~

Since stage ~5~ finishes last at time ~31~, we output ~31~.

Input 2

4 3
1 2
1 3
3 4
5 3 2 7

Output 2

14

The stages and their dependencies are:

1 → 2
  ↘︎ 3 → 4

The optimal execution will be:

• Stage ~1~ finishes at time ~5~
• Stages ~2~ and ~3~ can be processed in parallel after stage ~1~, finishing at time ~8~ and ~7~ respectively
• Stage ~4~ starts at time ~7~ after stage ~3~ finishes, and finishes at time ~14~