output_description: Print the K-th lexicographically smallest substring of K.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      s
      K
attempt: class Bit:
      def __init__(self, n):
          self.bl = n.bit_length()
          self.size = n
          self.tree = [0] * (n + 1)
  
      def sum(self, i):
          s = 0
          while i > 0:
              s += self.tree[i]
              i -= i & -i
          return s
  
      def add(self, i, x):
          while i <= self.size:
              self.tree[i] += x
              i += i & -i
  
  
  import sys
  
  input = sys.stdin.readline
  from copy import deepcopy
  
  
  def main():
      n = int(input())
      ca = [input().rstrip() for i in range(2 * n)]
      dc = [0] * (2 * n + 1)
      for i in range(2 * n):
          if ca[i][0] == "W":
              dc[int(ca[i][2])] = i + 1
          else:
              dc[n + int(ca[i][2])] = i + 1
      dp = [[10**7 for i in range(n + 1)] for j in range(n + 1)]
      dp[0][0] = 0
      bit0 = Bit(2 * n)
      for i in range(n + 1):
          wx = dc[i + 1]
          if i:
              bit0.add(dc[i], 1)
          if i < n:
              dp[i + 1][0] = dp[i][0] + wx - bit0.sum(wx) - 1
          bitc = deepcopy(bit0)
          for j in range(n + 1):
              if j < n:
                  bx = dc[n + j + 1]
                  dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + bx - bitc.sum(bx) - 1)
                  bitc.add(bx, 1)
              if i < n:
                  dp[i + 1][j] = dp[i][j] + wx - bitc.sum(wx) - 1
      print(dp[-1][-1])
  
  
  main()
  
problem_description: Statement
  
  You are given a string s. Among the **different** substrings of s, print the
  K-th lexicographically smallest one.
  
  A substring of s is a string obtained by taking out a non-empty contiguous
  part in s. For example, if s = `ababc`, `a`, `bab` and `ababc` are substrings
  of s, while `ac`, `z` and an empty string are not. Also, we say that
  substrings are different when they are different as strings.
  
  Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings.
  X is lexicographically larger than Y if and only if Y is a prefix of X or
  x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.
samples: [{"input": "aba\n    4", "output": "b\n    \n\ns has five substrings: `a`, `b`, `ab`, `ba` and `aba`. Among them, we should\nprint the fourth smallest one, `b`. Note that we do not count `a` twice.\n\n* * *"}, {"input": "atcoderandatcodeer\n    5", "output": "andat\n    \n\n* * *"}, {"input": "z\n    1", "output": "z"}]