Wise Business

2.5

2 votes
Topological Sort, Algorithms, Graphs
Problem

You just graduated from the business school of MagicLand and are about to start your own business. You will be buying some magical potions from the great wizard of MagicLand and selling them at your hometown HackerLand.
The great wizard sells N different types of potions where the ith (1<=i<=N) potion is of the price A[i]. You can convert a potion of type X[i] to a potion of type Y[i] (1<=i<=M).
The conversion of potion from one type to another is unidirectional.
What is the maximum amount of profit you can make from buying and selling a single potion?

Input Format:

  • The first line contains T, denoting the number of test cases.
  • The first line of each test case has two space-separated integers, N & M, representing the number of different types of potions and the number of different kinds of conversions you can make, respectively.
  • The following line contains N space-separated integers representing the array A, where A[i] is the price of a potion of the ith type.
  • The ith of the next M lines contains two space-separated integers, X[i] & Y[i], denoting that you can convert a potion of type X[i] to a potion of type Y[i].


Output Format:
For each test case, print a single integer representing the maximum possible profit.

Constraints:
1<=T<=5
2<=N<=105
1<=M<=min(N(N1)/2,105)
1<=A[i]<=105
(X[i],Y[i])!=(X[j],Y[j]),i!=j
There is no way to convert any potion to a potion of the same type with at least one conversion.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, we can buy a potion of type 1 and convert it to a type 2 before selling. Therefore, profit = 9 - 3 = 6.

In the second test case, we can buy any potion and then sell it without conversion, which only reduces the price.

Editor Image

?