Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
from heapq import *
def input(): return sys.stdin.readline().strip()


def main():
    s = input()
    L = len(s)
    K = int(input())
    string = set([])
    for i in range(L):
        for j in range(i + 1, L + 1):
            string.add(s[i:j])

    string = list(string)
    heapify(string)
    for _ in range(K):
        ans = heappop(string)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from heapq import *
def input(): return sys.stdin.readline().strip()


def main():
    """
    文字列のソートをする際には計算量に要注意！
    数字の大小比較と違って文字列の比較の場合は１文字１文字左から順番に見ないといけない。
    そのため一回の比較でO(比較文字列の長さ)分の計算量がかかる。
    特に長さMの文字列N個をソートするのにかかる時間は
            ❌O(NlogN)
            ⭕️O(MNlogN)

    そこで文字列のソート時には文字数をなるべく小さくするのがポイント。
    今回K<=5なので、「答えはK<=5文字以下になる」のがミソ。
    """

    s = input()
    L = len(s)
    K = int(input())
    string = set([])
    for i in range(L):
        for j in range(i + 1, min(i + K, L) + 1):
            string.add(s[i:j])

    string = list(string)
    heapify(string)
    for _ in range(K):
        ans = heappop(string)
    print(ans)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, K = map( int, input().split())
A = []
for i in range(N):
    a, b = map( int, input().split())
    A += [a]*b
A.sort()
print(A[K-1])

### FIXED CODE ###

N, K = map( int, input().split())
A = [ [0]*2 for _ in range(N)]
for i in range(N):
    A[i] = list(map( int, input().split()))
A.sort()
L = 0
for i in range(N):
    L += A[i][1]
    if L >= K:
        print(A[i][0])
        break
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
[print((max(a[:_] + a[_ + 1:]))) for _ in range(n)]


### FIXED CODE ###

import copy
n = int(input())
a = [int(input()) for _ in range(n)]
b = sorted(copy.copy(a), reverse=True)

for i in range(n):
    if a[i] == b[0]:
        print(b[1])
    else:
        print(b[0])
### BUGGY CODE ###

import numpy as np
n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
point=np.array([k]*n)
for i in range(q):
    point[:a[i]-1]-=1
    point[a[i]:]-=1
for i in range(n):
    if point[i]<=0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
point=[k-q]*n
for i in range(q):
    point[a[i]-1]+=1
for i in range(n):
    if point[i]>0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import bisect

s=input()
t=input()

#print(index)
condition=0
t2=list(set(t))
#print(t2)

for i in range(len(t2)):
 if s.count(t2[i])==0:
   condition=1
   break

if condition==1:
  print(-1)
else:
  index=list()
  for a in range(len(t)):
   index.append([i for i, x in enumerate(s) if x == t[a]])
  
  #print(index)
  b=index[0][0]
  j=1
  loop=0
  count=0
  if len(t)==1:
    print(b+1)
  else:
   while j <= len(t)-1:
     c=bisect.bisect_left(index[j],b-loop)
     #print(j,index[j],b,c,loop)
     if c < len(index[j]) and c != index[j][len(index[j])-1]:
        b=index[j][c]+loop
        #print(j,b,loop)
        j=j+1
        if j==len(t):
          print(b+1)
          break
     else:
        loop=loop+len(s)
        b=index[j][0]+loop
        j=j+1
        if j==len(t):
          print(b+1)
          break
        if loop == len(s)*(10**100):
           print(-1)
           break
        



### FIXED CODE ###

import bisect

s=input()
t=input()

#index=list()
#for a in range(len(t)):
# index.append([i for i, x in enumerate(s) if x == t[a]])

char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
for i, ch in enumerate(s):
    char_appear[ch].append(i)
#print(char_appear['a'])
      
b=0
loop=0
condition=0

for j in range(len(t)):
  if len(char_appear[t[j]])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect(char_appear[t[j]],b)
 # print(j,char_appear[t[j]],b,c,loop)
  if j<1:
    b=char_appear[t[0]][0]    
  elif c == len(char_appear[t[j]]): #or c==char_appear[t[j]][len(char_appear[t[j]])-1]: 
     loop +=1
     b=char_appear[t[j]][0]
     if loop==10**100:
        print(-1)
        condition=1
        break
  else:
     b=char_appear[t[j]][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)
### BUGGY CODE ###

N = int(input())
ans = 1
for i in range(N):
    ans *= i+1

ans = ans%(10**9+7)

print(ans)

### FIXED CODE ###

N = int(input())
ans = 1
for i in range(N):
    ans *= i+1
    ans = ans%(10**9+7)

print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
counter = 0

for k in range(2,N):
    for j in range(1,k):
        for i in range(j):
            if k-j==j-i or S[i]==S[j] or S[j]==S[k] or S[i]==S[k]:
                counter += 1

all = int(N*(N-1)*(N-2)/6)
print(all-counter)


### FIXED CODE ###

N = int(input())
S = input()
counter = 0

for i in range(N-2):
    for j in range(i+1,(N+i-1)//2+1):
        k = 2*j-i
        if not S[i]==S[j] and  not S[j]==S[k] and not S[i]==S[k]:
            counter += 1

rgb = S.count("R")*S.count("G")*S.count("B")
print(rgb-counter)
### BUGGY CODE ###

#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    # 愚直解
    N,K=pin()
    A=lispin()
    B=[0]*N
    B[0]=A[0]
    for j in range(1,N):
        B[j]=A[j]-A[j-1]
    #print(B)
    
    for k in range(K):
        temp=0
        C=[0]*N
        for i in range(N):
            temp+=B[i]
            #print(temp)
            if i-temp<0:

                C[0]+=1
            else:C[i-temp]+=1

            if i+temp+1<N:
                C[i+temp+1]-=1
        B=C[:]
    ans=[]
    x=0
    for c in C:
        x+=c
        ans.append(x)
    print(*ans)
#%%submit!
resolve()

### FIXED CODE ###

#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    # 愚直解
    N,K=pin()
    A=lispin()
    B=[0]*N
    B[0]=A[0]
    for j in range(1,N):
        B[j]=A[j]-A[j-1]
    #print(B)

    for k in range(K):
        temp=0
        C=[0]*N
        for i in range(N):
            temp+=B[i]
            #print(temp)
            if i-temp<0:

                C[0]+=1
            else:C[i-temp]+=1

            if i+temp+1<N:
                C[i+temp+1]-=1
        B=C[:]
        if B[0]==N and sum(B)==N:
            break
    ans=[]
    x=0
    for c in C:
        x+=c
        ans.append(x)
    print(*ans)
    #after contest
    
#%%submit!
resolve()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
import sys
sys.setrecursionlimit(10**5+10) 
def up(i,pre):
    if i == len(A) - 1:
        return abs(A[pre] - A[i])
    res1 = res2 = float("inf")
    res1 = up(i + 1,i)
    if i + 2 <=len(A) -1: 
        res2 = up(i + 2,i)
    return min(abs(A[pre] - A[i]) + res1,abs(A[pre] - A[i]) + res2)

if N > 2:
    print(min(up(1,0),up(2,0)))
else:
    print(up(1,0))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [0 for _ in range(len(A))]
dp[0] = 0 
for i in range(1,N):
    if i - 2>=0:
        dp[i] = min(dp[i-1] + abs(A[i] - A[i-1]),dp[i-2] + abs(A[i] - A[i-2]))
    else:
        dp[i] =dp[i-1] + abs(A[i] - A[i-1])

print(dp[len(A)-1])
### BUGGY CODE ###

import math
k = int(input())
 
 
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += math.gcd(a, math.gcd(b, c))
print(ans)

### FIXED CODE ###

from math import gcd
k = int(input())
 
 
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, gcd(b, c))
print(ans)
### BUGGY CODE ###

# Problem C - Repsept
# input
K = int(input())

# initialization
seven = 7
ans = 1

# count
if K%2==0 and K%5==0:
    ans = -1
elif K==1:
    ans = 1
else:
    tmp_list = [0]*(10**6+1)
    while not seven%K==0: # 割り切れない限り
        seven = seven*10 + 7
        seven = seven % K
        ans += 1


# output
print(ans)


### FIXED CODE ###

# Problem C - Repsept
# input
K = int(input())

# initialization
seven = 7
ans = 1

# count
if K%2==0 or K%5==0:
    ans = -1
elif K==1:
    ans = 1
else:
    tmp_list = [0]*(10**6+1)
    while not seven%K==0: # 割り切れない限り
        seven = seven*10 + 7
        seven = seven % K
        ans += 1


# output
print(ans)
### BUGGY CODE ###

import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = {}
    for _ in range(M):
        (A,B) = map(int, input().split())
        na = neighbor.get(A, [])
        nb = neighbor.get(B, [])
        neighbor.update({A:(na+[B])})
        neighbor.update({B:(nb+[A])})

    guide = {1:1}

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    checked = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor.get(n, [])
        # すでに道しるべがあるものは除く
        dests = filter(lambda d: not d in checked, dests)
        # 道しるべを置く
        for d in dests:
            guide.update({d:n})
            checked += d,
            # 探索候補の末尾に追加
            target += d,

    print('Yes')
    for i in range(2,N+1):
        print(guide[i])

main()


### FIXED CODE ###

#import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    (N, M) = map(int, input().split())
    neighbor = [[] for _ in range(N+1)]
    for _ in range(M):
        (A,B) = map(int, input().split())
        neighbor[A] += B,
        neighbor[B] += A,

    guide = [0 for _ in range(N+1)]

    # 1の部屋から幅優先で道しるべを置く
    
    # 探索候補
    target = [1]
    checked = [1]
    while len(target) > 0:
        # 候補の先頭から取る
        n = target.pop(0)
        # nから伸びる行き先
        dests = neighbor[n]
        # すでに道しるべがあるものは除く
        dests = filter(lambda d: guide[d] == 0, dests)
        # 道しるべを置く
        for d in dests:
            guide[d] = n
            checked += d,
            # 探索候補の末尾に追加
            target += d,

    print('Yes')
    for i in range(2,N+1):
        print(guide[i])

main()
### BUGGY CODE ###

import math

def prime(n):
    for i in range(2, int(n/2)+1):
        if  n % i == 0:
            return False
    return True

num_prime = []
k = 0
while True:
    try:
        n = input()
    except:
        break
    if prime(int(n)):
        if not int(n) in num_prime:
            k += 1
            num_prime.append(int(n))

print(k)

### FIXED CODE ###

import math

def prime(n):
    for i in range(2, int(math.sqrt(n))+1):
        if  n % i == 0:
            return False
    return True

num_prime = []
k = 0
while True:
    try:
        n = input()
    except:
        break
    if prime(int(n)):
        if not int(n) in num_prime:
            k += 1
            num_prime.append(int(n))

print(k)
### BUGGY CODE ###

n=int(input())
al=[int(input()) for _ in range(n)]

setal=set(al)
ans=0
for seta in setal:
    if al.count(seta)%2 == 1:
        ans+=1

print(ans)

### FIXED CODE ###

n=int(input())
s=set()
for _ in range(n):
    a = input()
    if a in s:
        s.remove(a)
    else:
        s.add(a)
print(len(s))
### BUGGY CODE ###

n, m = map(int, input().split())
lrl = list(list(map(int, input().split())) for _ in range(m))
idl = [0]*n

for lr in lrl:
    for i in range(lr[0]-1, lr[1]):
        idl[i] += 1

print(idl.count(m))




### FIXED CODE ###

n, m = map(int, input().split())
lrl = list(list(map(int, input().split())) for _ in range(m))
lmax = 0
rmin = n

for lr in lrl:
    if lr[0] > lmax:
        lmax = lr[0]
    if lr[1] < rmin:
        rmin = lr[1]
if lmax <= rmin:
    print(rmin-lmax+1)
else:
    print(0)
### BUGGY CODE ###

N = int(input())
words = [input() for i in range(N)]

word = list(set(words))
counter = list()
dict = {}

for a in word:
    counter.append(words.count(a))

max = max(counter)

for a,b in zip(word,counter):
    dict[a] = b

for a in word:
    if dict[a] == max:
        continue
    else:
        del dict[a]

dict2 = sorted(dict.keys())

for a in dict2:
    print(a)

### FIXED CODE ###

N = int(input())
words = [input() for i in range(N)]

from collections import Counter

word = list(set(words))

dict = Counter(words)

max = max(dict.values())

for a in word:
    if dict[a] == max:
        continue
    else:
        del dict[a]

dict2 = sorted(dict.keys())

for a in dict2:
    print(a)
### BUGGY CODE ###

n = int(input())
lst = list(map(int,input().split()))
ans = 0
for i in range(len(lst)):
    if (lst.count(lst[i]) != 1):
        ans = 1

if (ans == 0):
    print("YES")
else:
    print("NO")


### FIXED CODE ###

n = int(input())
lst = list(map(int,input().split()))
x = len(lst)
lst = list(set(lst))
y = len(lst)

if (x == y):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = l[i]
        b = l[j]
        x = (a+1) - b
        y = (b+1) - a
        z = max(x,y)
        a = j+1
        b = n-1
        c = (a+b) // 2
        while a <= b:
            if l[c] == z:
                a += 1
            elif l[c] > z:
                a = c + 1
            elif l[c] < z:
                b = c - 1
            else:
                pass
            c = (a+b) // 2
        ans += c-j
print(ans)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort(reverse=True)
ans = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        a = l[i]
        b = l[j]
        x = (a+1) - b
        y = (b+1) - a
        z = max(x,y)
        a = j+1
        b = n-1
        c = (a+b) // 2
        while a <= b:
            if l[c] == z:
                a += 1
            elif l[c] > z:
                a = c + 1
            elif l[c] < z:
                b = c - 1
            else:
                pass
            c = (a+b) // 2
        ans += c-j
print(ans)
### BUGGY CODE ###

def solve(N, W, weightValues):
    dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
    for i in range(1, N + 1):
        w, v = weightValues[i - 1]
        for j in range(1, W + 1):
            if j < w:  # you cant take it
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
    print(dp[N][W])


def iln(): return list(map(int, input().split()))


N, W = iln()
w_v = []
for i in range(N):
    w_v.append(iln())

solve(N, W, w_v)

### FIXED CODE ###


N,W=map(int,input().split())
dp=[0]*(W+1)
L = sorted([list(map(int,input().split())) for i in range(N)])
s=0
 
for w, v in L:
    s+=w
    for j in range(min(W,s),w-1,-1):
        if dp[j-w]+v > dp[j]: dp[j]=dp[j-w]+v
    
print(max(dp))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int, input().split())
A = list(map(int, input().split()))

for i in range(M):
	b, c = map(int, input().split())
	A += [c]*b
A.sort(reverse=True)
B = A[0:N]
print(sum(B))


### FIXED CODE ###

import sys, heapq
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''

N, M = map(int, input().split())
A = list(map(int, input().split()))
a = [(-i, 1) for i in A]
heapq.heapify(a)

for i in range(M):
	b, c = map(int, input().split())
	heapq.heappush(a, (-c, b))
	
ans = 0

for i in range(N):
	pop = heapq.heappop(a)
	ans += pop[0]
	if pop[1] != 1:
		heapq.heappush(a, (pop[0], pop[1] - 1))

ans *= -1
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())

comb = [[0 for j in range(n+1)] for i in range(n+1)]

for i in range(n+1):
    for j in range(n+1):
        if j == 0 or j == i:
            comb[i][j] = 1
        elif j < 0 or j > i:
            comb[i][j] = 0
        else:
            comb[i][j] = (comb[i-1][j] + comb[i-1][j-1])%(10**9+7)


for i in range(1,k+1):
    print((comb[n-k+1][i]*comb[k-1][i-1])%(10**9+7))

### FIXED CODE ###

n,k = map(int,input().split())

comb = [[0 for j in range(i+1)] for i in range(n+1)]

for i in range(n+1):
    for j in range(i+1):
        if j == 0 or j == i:
            comb[i][j] = 1
        elif j < 0 or j > i:
            comb[i][j] = 0
        else:
            comb[i][j] = (comb[i-1][j] + comb[i-1][j-1])%(10**9+7)


for i in range(1,k+1):
    if n-k+1 < i:
        print(0)
    else:
        print((comb[n-k+1][i]*comb[k-1][i-1])%(10**9+7))
### BUGGY CODE ###

import heapq

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [a-1 for a in r]
paper = set()
T = [[] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    T[a].append((c,b))
    T[b].append((c,a))

memo = {}
def distance(a,b):
    #print('distance(',a,',',b,') =?')
    if a > b:
        a,b = b,a
    if (a,b) in memo.keys():
        return memo[(a,b)]
    q = []
    heapq.heappush(q, (0,a))
    try:
        while True:
            c, t = heapq.heappop(q)
            if t == b:
                memo[(a,b)] = c
                #print('distance(',a,',',b,') =',c)
                return c
            for i in T[t]:
                heapq.heappush(q, (c+i[0],i[1]))
    except IndexError:
        pass

inf = 1 << 60
arrived = [False] * R
def calc(src, rest):
    if rest == 0:
        return 0
    ret = inf
    for i in range(R):
        if not arrived[i]:
            arrived[i] = True
            ret = min(ret, distance(src,r[i]) + calc(r[i], rest-1))
            arrived[i] = False
    return ret

ans = inf
for i in range(R):
    arrived[i] = True
    ans1 = calc(r[i], R-1)
    #print('ans1',ans1)
    ans = min(ans, ans1)
    arrived[i] = False

print(ans)


### FIXED CODE ###

import heapq

N,M,R = map(int,input().split())
r = list(map(int,input().split()))
r = [a-1 for a in r]
paper = set()
T = [[] for i in range(N)]
for i in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    T[a].append((c,b))
    T[b].append((c,a))

inf = 1 << 60
memo = {}
def distance(a,b):
    #print('distance(',a,',',b,') =?')
    if (a,b) in memo.keys():
        #print('distance(',a,',',b,') =',memo[(a,b)])
        return memo[(a,b)]
    d = [inf] * N
    d[a] = 0
    q = []
    heapq.heappush(q, (0,a))
    try:
        while True:
            c, t = heapq.heappop(q)
            if t == b:
                memo[(a,b)] = c
                memo[(b,a)] = c
                #print('distance(',a,',',b,') =',c)
                return c
            for i in T[t]:
                if d[i[1]] > c + i[0]:
                    d[i[1]] = c + i[0]
                    heapq.heappush(q, (c + i[0], i[1]))

    except IndexError:
        pass

arrived = [False] * R
ans = inf

def calc(src, rest, total):
    global ans
    if total >= ans:
        return
    if rest == 0:
        ans = min(ans,total)
        return

    for i in range(R):
        if not arrived[i]:
            arrived[i] = True
            calc(r[i], rest-1, total + distance(src,r[i]))
            arrived[i] = False

for i in range(R):
    arrived[i] = True
    calc(r[i], R-1, 0)
    arrived[i] = False

print(ans)
### BUGGY CODE ###

s=input()

l=[0]
ans=[0]*(len(s))
for i in range(len(s)-1):
    if s[i]=="L" and s[i+1]=="R":
        l.append(i+1)
       
n=len(l)+1
l.append(len(s))
#print(set(s[l[0]:l[1]]))

for i in range(n-1):
    #print(s[l[i]:l[i+1]])
    for j in range(len(s[l[i]:l[i+1]])-1):
        p=len(s[l[i]:l[i+1]])
        if s[l[i]:l[i+1]][j]=="R" and s[l[i]:l[i+1]][j+1]=="L":
            if j%2==1:
                ans[l[i]+j]=p//2
                ans[l[i]+j+1]=p-p//2
            else:
                ans[l[i]+j]=p-p//2
                ans[l[i]+j+1]=p//2
        else:
            if set(s[l[i]:l[i+1]])=={"L"}:
                ans[l[i]]=p
            elif set(s[l[i]:l[i+1]])=={"R"}:
                ans[l[i+1]-1]=p
print(*ans)


            
  


### FIXED CODE ###

s=input()

l=[0]
ans=[0]*(len(s))
for i in range(len(s)-1):
    if s[i]=="L" and s[i+1]=="R":
        l.append(i+1)
       
n=len(l)+1
l.append(len(s))
#print(set(s[l[0]:l[1]]))

for i in range(n-1):
    #print(s[l[i]:l[i+1]])
    for j in range(len(s[l[i]:l[i+1]])-1):
        p=len(s[l[i]:l[i+1]])
        if s[l[i]]=="L":
            ans[l[i]]=p
            break
        if s[l[i+1]-1]=="R":
            ans[l[i+1]-1]=p
            break
        if s[l[i]:l[i+1]][j]=="R" and s[l[i]:l[i+1]][j+1]=="L":
            if j%2==1:
                ans[l[i]+j]=p//2
                ans[l[i]+j+1]=p-p//2
                break
            else:
                ans[l[i]+j]=p-p//2
                ans[l[i]+j+1]=p//2
                break
print(*ans)
### BUGGY CODE ###

# C - Good Sequence
# coding: utf-8

N = int(raw_input())
a = map(int, raw_input().split())
result = 0

while a != []:
  first_num = a[0]
  first_count = a.count(first_num)
  result += first_count if first_num > first_count else first_count-first_num
  a = [num for num in a if num is not first_num]

print result

### FIXED CODE ###

# C - Good Sequence
# coding: utf-8

from collections import Counter

N = int(raw_input())
a = map(int, raw_input().split())
result = 0
cnt = Counter()

for num in a: cnt[num] += 1

for x, y in cnt.items():
  result += y if x>y else y-x

print result
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from itertools import accumulate


def solve():
    N, M = map(int, input().split())
    if N <=M :
        *T, = map(int, input().split())
        S = map(int, input().split())
        dp = [0]*(N+1)
    else:
        S = map(int, input().split())
        *T, = map(int, input().split())
        dp = [0]*(M+1)
    for s in S:
        *dp, = map(int.__add__, dp, accumulate(map(lambda d,t: (d+1 if s.__eq__(t) else 0), [0]+dp, T)))
    res = (dp[-1]+1)%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [1]*(M+1)
    for s in S:
        is_s = s.__eq__
        dp_ = dp[:]
        acc = 0
        for i, t in enumerate(T):
            if is_s(t):
                acc += dp_[i]
            dp[i+1] = dp_[i+1] + acc
    res = (dp[-1])%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr=sorted(arr,reverse=True,key=lambda x:x[1])
arr=sorted(arr,reverse=True,key=lambda x:x[0])
q=[]
tmp=0
cnt=0
for a,b in arr:
  if tmp!=a:
    tmp=a
    cnt=0
  if m-tmp<cnt:
    continue
  heapq.heappush(q,(-b,a))
  cnt+=1
ans=0
cnt=0
box=[0]*(m+1)
while len(q)!=0:
  if cnt>=m:
    break
  tmp,date=heapq.heappop(q)
  if box[date]==0:
    box[date]=1
    ans-=tmp
    cnt+=1
  else:
    pos=date
    while 1:
      if pos==m:
        break
      pos+=1
      if box[pos]==0:
        box[pos]=1
        ans-=tmp
        cnt+=1
        break
print(ans)

### FIXED CODE ###

import heapq

n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
arr2=[[i,0] for i in range(1,m+5)]
arr.extend(arr2)
arr=sorted(arr,reverse=True,key=lambda x:x[1])
arr=sorted(arr,key=lambda x:x[0])
tmp=arr[0][0]
q=[]
ans=0
pos=0
while 1:
  a,b=arr[pos]
  if a>m:
    break
  if a==arr[pos+1][0]:
    heapq.heappush(q,-b)
  else:
    heapq.heappush(q,-b)
    ans-=heapq.heappop(q)
  pos+=1
print(ans)