My solution is in Python, though my algorithm sucks. I wrote this with around 10 minutes to go in the competition, and I think from memory I only passed 6/10 test cases. Algorithmic complexity is O(x^2) - which, when talking to someone who had the same complexity in their C++ algorithm, passed 7/10 test cases. My conclusion therefore is to next year use C++ and not Python :p

Any suggestions to improve on the algorithm are welcome.
Spoiler:
I've included a sample test case.

Code:
def solve(cities):
  calculated = []
  total = 0
  keys = cities.keys()
  keys.sort()
  elements = []
  for key in keys:
    elements.append(key)
  count = 0
  for i in range(0, len(elements)):
    for x in range(i + 1, len(elements)):
      count += 1
      total += (elements[x] - elements[i]) * max(cities[elements[i]], cities[elements[x]])
  print count
  return total % 1000000007

search = """2
3
1 3 6
10 20 30
5
5 55 555 55555 555555
3333 333 333 33 35"""
lines = search.split("\n")

try:
  for i in range(0, len(lines)):
    if i == 0:
      amount = lines[i]
    else:
      if i % 3 == 1:
        limit = int(lines[i])
      elif i % 3 == 2:
        towns = lines[i].split(" ", limit)
      elif i % 3 == 0:
        population = lines[i].split(" ", limit)
        town = {}
        for x in range(0, len(towns)):
          town[int(towns[x])] = int(population[x])
        print solve(town)
except:
  pass