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 i′th (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:
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∗(N−1)/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.
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.