output_description: Find the minimum number of moves required to achieve the objective.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N M
      X_1 X_2 ... X_M
attempt: debug = 0
  """
  N: state num
  M: city num
  """
  
  
  if debug:
      N = 2
      m = 10
  else:
      (N, M) = list(map(int, input().split()))
  
  if debug:
      p_y_list = [
          [1, 30],
          [1, 20],
          [1, 10],
          [1, 3],
          [2, 63],
          [2, 33],
          [2, 23],
          [3, 21],
          [3, 7],
      ]
  
  city_id_list = []
  for num, z in enumerate(range(M)):
      # for num, (P, Y) in enumerate(p_y_list):
  
      if not debug:
          (P, Y) = list(map(int, input().split()))
  
      city_id_list.append([Y, P, num])
  
  city_id_list = sorted(city_id_list, key=lambda x: x[0])
  
  state_cnt = {}
  tmp_list = []
  for Y, P, num in city_id_list:
  
      if P not in state_cnt.keys():
          state_cnt[P] = 1
      elif P in state_cnt.keys():
          state_cnt[P] += 1
  
      tmp_id = str(P).zfill(6) + str(state_cnt[P]).zfill(6)
  
      tmp_list.append([num, tmp_id])
  
  for cid in sorted(tmp_list, key=lambda x: x[0]):
      print(cid[1])
  
problem_description: Statement
  
  We will play a one-player game using a number line and N pieces.
  
  First, we place each of these pieces at some integer coordinate.
  
  Here, multiple pieces can be placed at the same coordinate.
  
  Our objective is to visit all of the M coordinates X_1, X_2, ..., X_M with
  these pieces, by repeating the following move:
  
  **Move** : Choose a piece and let x be its coordinate. Put that piece at
  coordinate x+1 or x-1.
  
  Note that the coordinates where we initially place the pieces are already
  regarded as visited.
  
  Find the minimum number of moves required to achieve the objective.
samples: [{"input": "2 5\n    10 12 1 2 14", "output": "5\n    \n\nThe objective can be achieved in five moves as follows, and this is the\nminimum number of moves required.\n\n  * Initially, put the two pieces at coordinates 1 and 10.\n  * Move the piece at coordinate 1 to 2.\n  * Move the piece at coordinate 10 to 11.\n  * Move the piece at coordinate 11 to 12.\n  * Move the piece at coordinate 12 to 13.\n  * Move the piece at coordinate 13 to 14.\n\n* * *"}, {"input": "3 7\n    -10 -3 0 9 -100 2 17", "output": "19\n    \n\n* * *"}, {"input": "100 1\n    -100000", "output": "0"}]