output_description: Print the smallest initial amount of money W that enables you to win the game.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      A_1 B_1
      A_2 B_2
      :
      A_N B_N
      U_1 V_1
      U_2 V_2
      :
      U_M V_M
attempt: N, K, Q = [int(i) for i in input().split(" ")]
  A = [int(a) for a in input().split(" ")]
  
  _min = min(A)
  A.sort()
  for k in range(K):
      _max = A.pop(0)
  print(_max - _min)
  
problem_description: Statement
  
  There is a simple undirected graph with N vertices and M edges. The vertices
  are numbered 1 through N, and the edges are numbered 1 through M. Edge i
  connects Vertex U_i and V_i. Also, Vertex i has two predetermined integers A_i
  and B_i. You will play the following game on this graph.
  
  First, choose one vertex and stand on it, with W yen (the currency of Japan)
  in your pocket. Here, A_s \leq W must hold, where s is the vertex you choose.
  Then, perform the following two kinds of operations any number of times in any
  order:
  
    * Choose one vertex v that is directly connected by an edge to the vertex you are standing on, and move to vertex v. Here, you need to have at least A_v yen in your pocket when you perform this move.
    * Donate B_v yen to the vertex v you are standing on. Here, the amount of money in your pocket must not become less than 0 yen.
  
  You win the game when you donate once to every vertex. Find the smallest
  initial amount of money W that enables you to win the game.
samples: [{"input": "4 5\n    3 1\n    1 2\n    4 1\n    6 2\n    1 2\n    2 3\n    2 4\n    1 4\n    3 4", "output": "6\n    \n\nIf you have 6 yen initially, you can win the game as follows:\n\n  * Stand on Vertex 4. This is possible since you have not less than 6 yen.\n  * Donate 2 yen to Vertex 4. Now you have 4 yen.\n  * Move to Vertex 3. This is possible since you have not less than 4 yen.\n  * Donate 1 yen to Vertex 3. Now you have 3 yen.\n  * Move to Vertex 2. This is possible since you have not less than 1 yen.\n  * Move to Vertex 1. This is possible since you have not less than 3 yen.\n  * Donate 1 yen to Vertex 1. Now you have 2 yen.\n  * Move to Vertex 2. This is possible since you have not less than 1 yen.\n  * Donate 2 yen to Vertex 2. Now you have 0 yen.\n\nIf you have less than 6 yen initially, you cannot win the game. Thus, the\nanswer is 6.\n\n* * *"}, {"input": "5 8\n    6 4\n    15 13\n    15 19\n    15 1\n    20 7\n    1 3\n    1 4\n    1 5\n    2 3\n    2 4\n    2 5\n    3 5\n    4 5", "output": "44\n    \n\n* * *"}, {"input": "9 10\n    131 2\n    98 79\n    242 32\n    231 38\n    382 82\n    224 22\n    140 88\n    209 70\n    164 64\n    6 8\n    1 6\n    1 4\n    1 3\n    4 7\n    4 9\n    3 7\n    3 9\n    5 9\n    2 5", "output": "582"}]