Subsequence Weighting solution

cases = int(raw_input())
for i in range(cases):
  numlen = int(raw_input())
  ints = [int(x) for x in raw_input().split(' ')]
  weights = [int(x) for x in raw_input().split(' ')]
  # Array of pairs of integers and the total score that can be attained going up to that
  # integer - eg. given pairs [1,10],[2,20],[3,30],[4,40],[1,15],[2,15],[3,15],[4,50]
  # we would have in this array [1,10] (and [1,15] eventually), [2,30], [3,60], etc
  inttoscore = [[0,0]]
  for i in range(len(ints)):
    # Binary search our way to the weight
    left,right = 0,len(inttoscore)-1
    while right-left > 1:
      ave = int((left+right)/2)
      if ints[i] > inttoscore[ave][0]: left = ave
      else: right = ave
    if ints[i] < inttoscore[left][0]: place = left
    elif ints[i] < inttoscore[right][0]: place = right
    else: place = right + 1
    while place > 0 and ints[i] == inttoscore[place-1][0]:
      place -= 1
    inttoscore.insert(place,[ints[i],weights[i] + inttoscore[place-1][1]])
    while place+1 < len(inttoscore) and inttoscore[place][1] >= inttoscore[place+1][1]: inttoscore.pop(place+1)
  #print ints, weights, scores
  print inttoscore[-1][1]