Sumo là một đứa trẻ rất thích đi du lịch qua những ngọn núi. Có ~N~ điểm trên các ngọn núi, mỗi điểm sẽ có một độ cao là ~H[i]~ được nối với nhau bởi M tuyến đường một chiều. Sumo nghĩ rằng một hành trình được cho là đặc biệt nhất nếu ~H[điểm kết thúc]~ – ~H[điểm xuất phát]~ có giá trị lớn nhất. Nhiệm vụ của bạn là giúp Sumo tìm ra giá trị ~H[điểm kết thúc]~ – ~H[điểm xuất phát]~ lớn nhất có thể.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên ~T~ là số bộ testcase

Với mỗi testcase

• Dòng đầu tiên chứa 2 số ~N~ và ~M~

• Dòng thứ hai chứa ~N~ số nguyên, số nguyên thứ i biểu diễn cho ~H[i]~

• ~M~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~a_i~ và ~b_i~.

Dữ liệu ra:

• Với mỗi test case ghi ra trên một dòng, một số nguyên duy nhất là giá trị chênh lệch chiều cao lớn nhất

Ràng buộc:

• ~1 \le T \le 10~

• ~0 \le H[i] \le 10^9~

• ~1 \le a_i,b_i ~ N~

SUBTASK

• Subtask 1: ~1 \le N \le 1000~; ~1 \le N \le 2000~

• Subtask 2: ~1 \le N \le 10^5~; ~1 \le N \le 2*10^5~.

Ví dụ:

Input:

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

Output:

5