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

S = list(input())
Q = int(input())
for i in range(Q):
    query = input().split()
    if int(query[0]) == 1:
        S.reverse()
    else:
        if int(query[1]) == 1:
            S = list("{0}{1}".format(query[2], "".join(S)))
        else:
            S = list("{0}{1}".format("".join(S), query[2]))
print("".join(S))


### FIXED CODE ###

from collections import deque
S = deque(list(input()))
Q = int(input())
t = 0
for i in range(Q):
    query = input().split()
    if int(query[0]) == 1:
        t += 1
    else:
        query[1] = int(query[1])
        if t % 2 == 1:
            if query[1] == 1:
                query[1] = 2
            else:
                query[1] = 1
        if query[1] == 1:
            S.appendleft(query[2])
        else:
            S.append(query[2])
if t % 2 == 1:
    S.reverse()
print("".join(S))
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]

players = np.array([K] * N)
for a in A:
    players = players - 1
    players[a-1] += 1
    
for p in players:
    if p > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import numpy as np
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]

players = list(np.array([K - len(A)] * N))
for a in A:
    players[a-1] += 1
    
for p in players:
    if p > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
cost = [[float("inf") for i in range(n)] for i in range(n)] 
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[1000000]*n    

que=deque([])
que.append(0)
while(len(que)):
    v=que.popleft()
    for i in to[v]:
        if(dist[i] is 1000000):
            dist[i]=v+1
            que.append(i)
        
print("Yes")
for i in dist[1:]:
    print(i)    


### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
to=[[] for i in range(n)]
for i in range(m):
    x,y = map(int,input().split())
    to[x-1].append(y-1)
    to[y-1].append(x-1)
dist=[None]*n    

que=deque([0])
while que:
    v=que.pop()
    for i in to[v]:
        if(dist[i] is None):
            dist[i]=v+1
            que.appendleft(i)
        
print("Yes")
for i in dist[1:]:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N = int(input())
MOD = 10**9 + 7

neighbor = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    neighbor[x-1].append(y-1)
    neighbor[y-1].append(x-1)

memo = [[-1]*2 for _ in range(N)]

def dp(node, color, parent):
    if memo[node][color] != -1:
        return memo[node][color]
    output = 1
    for child in neighbor[node]:
        if child == parent:
            pass
        else:
            tmp = dp(child, 0, node)
            if color == 0:
                tmp += dp(child, 1, node)
                tmp %= MOD
            output *= tmp
            output %= MOD
    memo[node][color] = output
    return output

print((dp(0,0,-1) + dp(0,1,-1)) % MOD)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N, *XY = map(int,open(0).read().split())
MOD = 10**9 + 7

neighbor = [[] for _ in range(N)]
for x,y in zip(*[iter(XY)]*2):
    neighbor[x-1] += y-1,
    neighbor[y-1] += x-1,

parent = {0}

def dp(node):
    black_output = white_output = 1
    for child in neighbor[node]:
        if child in parent:
            continue
        else:
            parent.add(child)
            tmp_black, tmp_white = dp(child)
            black_output *= tmp_white
            white_output *= tmp_black + tmp_white
    black_output %= MOD
    white_output %= MOD
    return black_output, white_output

print(sum(dp(0)) % MOD)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def main():
    N, M = mi()
    A = sorted(li())

    '''
    for j in range(M):
        b, c = mi()
        ind = min(bisect.bisect_left(A, c), b)
        A = sorted([c]*ind + A[ind:])
    
    print(sum(A))
    '''
    for j in range(M):
        b, c = mi()
        A += [c]*b
    print(sum(sorted(A, reverse=True)[:N]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value

def main():
    N, M = mi()
    A = sorted(li())

    '''
    for j in range(M):
        b, c = mi()
        ind = min(bisect.bisect_left(A, c), b)
        A = sorted([c]*ind + A[ind:])
    
    print(sum(A))
    '''
    ab = li2(M)
    ab.sort(key=lambda x: x[1], reverse=True)
    c_list = []
    l = 0
    for b, c in ab:
        if l + b > N:
            c_list += [c]*(N-l)
            l = N
        else:
            c_list += [c]*b
            l += b
        if l == N:
            break
    ans = sum(sorted(A+c_list, reverse=True)[:N])
    print(ans)

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

#N　展望台の数　M　道の数
N,M = map(int, input().split())
#高さ
H =list(map(int,input().split()))

ans=[]
#道
J=[]
for i in range(M):
  J.append(list(map(int, input().split())))

for i in range(1,N+1):
  dic={}
  flg = 0
  for j in J:    
    if j[0] == i:
      dic.setdefault(j[1],0)
      dic[j[1]]+=1 
    elif j[1] == i:
      dic.setdefault(j[0],0)
      dic[j[0]]+=1
  
  if len(dic) == 0:
    ans.append(i)
  else:
    for k,v in dic.items():
      if H[k-1] >= H[i-1]:
        flg = 1
    if flg == 0:
      ans.append(i)

    
print(len(ans))

### FIXED CODE ###

#N　展望台の数　M　道の数
N,M = map(int, input().split())
#高さ
H =list(map(int,input().split()))

ans=0
di = {}
#道
J=[""]*M
for i in range(M):
  a,b=list(map(int, input().split()))
  di.setdefault(a,[])
  di[a].append(b)
  di.setdefault(b,[])
  di[b].append(a)
  
#  J[i]=(list(map(int, input().split())))

for i in range(1,N+1):
  flg = 0

  if i in di.keys():
#    print(i)
#    print(di[i])
    for k in di[i]:
      if H[k-1] >= H[i-1]:
        flg = 1
    if flg == 0:
      ans+=1

  else:
    ans+=1

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

N,K = map(int, input().split())
X = []; Y = []
oriX  = []; oriY = []


for i in range(N):
    x,y = map(int,input().split())
    oriX.append(x)
    oriY.append(y)
    X.append(x)
    Y.append(y)

X = sorted(list(set(X)))
Y = sorted(list(set(Y)))

for i in range(len( oriX)) :
    oriX[i] = X.index(oriX[i] )
    oriY[i] = Y.index( oriY[i] )  

MAP = [ [0] * len(oriX) for _ in (oriY)]
for i in range(len(oriX)):
    MAP[ oriY[i] ][ oriX[i] ] = 1


ans = float("inf")

for i in range(len(oriX)):
    for j in range(len(oriX)):
        if i == j : continue

        for p in range(len(oriY)):
            for q in range(len(oriY)):
                if p == q: continue


                npoints = 0
                for h in range(oriY[p], oriY[q]+1):
                    for w in range(oriX[i], oriX[j]+1):
                        if MAP[h][w] == 1: 
                            npoints += 1

                if npoints >= K:
                    tmp = (X[oriX[j]] - X[oriX[i]]) * (Y[oriY[q]] - Y[oriY[p]])
                    ans = min(tmp, ans)

print(ans)


### FIXED CODE ###

N,K = map(int, input().split())
XY = [ [int(j) for j in input().split()] for _ in range(N)]

xlst = []
ylst = []

for x,y in XY:
    x += 10**9 + 1
    y += 10**9 + 1
    xlst.append(x)
    ylst.append(y)

xset = sorted(list(set(xlst)))
yset = sorted(list(set(ylst)))

# print(xset, yset)

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

for x,y in zip(xlst,ylst):
    x=xset.index(x)+1
    y=yset.index(y)+1
    S[y][x] = 1

for y in range(N+1):
    for x in range(1, N+1):
        S[y][x] += S[y][x-1]
for x in range(N+1):
    for y in range(1,N+1):
        S[y][x] += S[y-1][x]


ans = float("inf")
for i in range(N):
    for j in range(N):
        for k in range(N):
            for ll in range(N):

                left     = xlst[i]
                right    = xlst[j]
                top      = ylst[k]
                bottom   = ylst[ll]

                if right <= left: continue
                if bottom <= top: continue

                left = xset.index(left)+1
                right = xset.index(right)+1
                top = yset.index(top)+1
                bottom=yset.index(bottom)+1


                cnt = 0
                cnt += S[bottom][right]
                # print(cnt)
                cnt += S[top-1][left-1]
                # print(cnt)
                cnt -= S[top-1][right]
                # print(cnt)
                cnt -= S[bottom][left-1]
                # print(cnt)
                if cnt >= K:
                    left = xset[left    -1 ]
                    right = xset[right  -1 ]
                    top = yset[top      -1 ]
                    bottom = yset[bottom-1 ]
                    rect_area = (right-left)*(bottom-top)
                    ans = min(ans, rect_area)
                
print(ans)
### BUGGY CODE ###

H,W,K=map(int,input().split())
S=[[] for i in range(0,H)]
for i in range(0,H):
    S[i]=input()

ans=10**4
for i in range(0,2**(H-1)):
    segment=[]
    start=0
    end=0
    for j in range(0,H-1):
        if (i>>j) & 1==1:
            end=j
            segment.append((start,end))
            start=end+1
    segment.append((start,H-1))
    white=[0 for j in range(0,len(segment))]
    count=0
    for j in range(0,W):
        for k in range(0,len(segment)):
            start,end=segment[k]
            white[k]+=sum((int(S[r][j])&1) for r in range(start,end+1))
        if max(white)>K:
            count+=1
            for k in range(0,len(segment)):
                start,end=segment[k]
                white[k]=sum((int(S[r][j])&1) for r in range(start,end+1))
            if max(white)>K:
                break
    else:
        test=count+len(segment)-1
        if test<ans:
            ans=test

print(ans)

### FIXED CODE ###

H,W,K=map(int,input().split())
S=[[] for i in range(0,H)]
for i in range(0,H):
    S[i]=input()

sumtable=[[0 for i in range(0,W)] for j in range(0,H+1)]
for i in range(1,H+1):
    for j in range(0,W):
        sumtable[i][j]=sumtable[i-1][j]+(int(S[i-1][j])&1)


ans=10**4
for i in range(0,2**(H-1)):
    segment=[]
    start=0
    end=0
    for j in range(0,H-1):
        if (i>>j) & 1==1:
            end=j
            segment.append((start,end))
            start=end+1
    segment.append((start,H-1))
    white=[0 for j in range(0,len(segment))]
    count=0
    for j in range(0,W):
        for k in range(0,len(segment)):
            start,end=segment[k]
            white[k]+=sumtable[end+1][j]-sumtable[start][j]
        if max(white)>K:
            count+=1
            for k in range(0,len(segment)):
                start,end=segment[k]
                white[k]=sumtable[end+1][j]-sumtable[start][j]
            if max(white)>K:
                break
    else:
        test=count+len(segment)-1
        if test<ans:
            ans=test

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

s = input()
while "ST" in s:
	s = s.replace("ST", "")
print(len(s))

### FIXED CODE ###

S = input()
cs = 0
ans = 0
for i in range(len(S)):
  si = S[i]
  if si == 'T' and cs > 0:
    cs -= 1
    ans += 2
  elif si == 'S':
    cs += 1
    
print(len(S)-ans)
### BUGGY CODE ###

n,w = map(int,input().split())
weight = [0] * n
value = [0] * n
dp = [ [0 for i in range(w + 1)] for j in range(n + 1)]
for i in range(n):
    weight[i], value[i] = map(int, input().split())

for i in range(n):
    for w in range(w + 1):
        if weight[i] <= w:
            dp[i + 1][w] = max(dp[i][w - weight[i]] + value[i], dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]
print(dp[n][w])


### FIXED CODE ###

N,W=map(int,input().split())
weight=[0]*N
value=[0]*N
for i in range(N):
    weight[i],value[i]=map(int,input().split())
dp=[[0 for i in range(W+1)] for j in range(N+1)]
for i in range(W+1):
    dp[0][i]=0

for i in range(N):
    for w in range(W+1):
        if weight[i]<=w:
            dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
        else:
            dp[i+1][w]=dp[i][w]
print(dp[N][W])
### BUGGY CODE ###

#ABC116D-VariousSushi.py

from sys import stdin
from numpy import sum

input = stdin.readline

N, K = [int(n) for n in input().split()]
INPUT = [[None for i in range(2)] for j in range(N)]
List1, List2 = [], []
kind1 = []

for i in range(N):
    INPUT[i][0], INPUT[i][1] = [int(m) for m in input().split()]

INPUT = sorted(INPUT, key = lambda x: (x[1], x[0]), reverse=True)

for i in range(N):
    if INPUT[i][0] not in kind1:
            List1.append([INPUT[i][1], 1])
            kind1.append(INPUT[i][0])
    else: List1.append([INPUT[i][1], 0])

List2 = List1[K:]
if List2 != []:
    List2.sort(key =lambda x : (x[1],x[0]))
    del List1[K:]
    lenList2 = len(List2)
else: lenList2 = 0

List1 = sorted(List1, key = lambda x : (x[1], x[0]), reverse=True)

sum = sum(List1, axis = 0)

Score = sum[0] + sum[1]**2
Test = Score
kindnumber = sum[1]

for i in range(lenList2):
    if List2[-1][1] == 0 or List1[-1][1] == 1:
        break
    Test = Test - List1.pop()[0] + List2.pop()[0] + 2 * kindnumber + 1
    kindnumber = kindnumber + 1
    if Test >= Score:
        Score = Test

print(int(Score))


### FIXED CODE ###

#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

INPUT.sort(key = lambda x: -x[1])

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)
### BUGGY CODE ###

class LazySegmentTree:
    """
    Range Max Query
    Node must be positive.
    """

    def __init__(self, n, sentinel=0):
        self.n = n
        self.n2 = 1 << (n + 1).bit_length()
        m = (self.n2 << 1) - 1
        self.data = [sentinel] * m
        self.lazy = [sentinel] * m
        self.flag = [False] * m
        self.sentinel = sentinel

    def _eval(self, i, l, r):
        if self.flag[i]:
            self.data[i] = max(self.data[i], self.lazy[i])
            if r - l > 1:
                li = (i << 1) + 1
                self.lazy[li] = max(self.lazy[li], self.lazy[i])
                self.lazy[li + 1] = max(self.lazy[li + 1], self.lazy[i])
                self.flag[li] = self.flag[li + 1] = True
            self.flag[i] = False

    def update(self, a, b, x, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return

        self._eval(i, l, r)

        if a <= l and r <= b:
            self.lazy[i] = x
            self.flag[i] = True
            self._eval(i, l, r)
        else:
            m = (l + r) // 2
            li = (i << 1) + 1
            self.update(a, b, x, li, l, m)
            self.update(a, b, x, li + 1, m, r)
            self.data[i] = max(self.data[li:li + 2])

    def get_max(self, a, b, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return self.sentinel

        self._eval(i, l, r)

        if a <= l and r <= b:
            return self.data[i]

        m = (l + r) // 2
        li = (i << 1) + 1
        return max(self.get_max(a, b, li, l, m), self.get_max(a, b, li + 1, m, r))


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
srt = sorted((h, i) for i, h in enumerate(hhh))
lst = LazySegmentTree(n, 0)

for h, i in srt:
    lst.update(i, lst.n2, lst.get_max(0, i) + aaa[i])
    # print(lst.data)
    # print(lst.lazy)
    # print(lst.flag)
print(lst.get_max(0, n))


### FIXED CODE ###

def solve(n, hhh, aaa):
    n2 = 1 << n.bit_length()
    offset = n2 - 1
    data = [0] * ((n2 << 1) - 1)

    def update(k, x):
        i = k + offset
        data[i] = max(data[i], x)
        while i:
            i = (i - 1) // 2
            data[i] = max(data[i], x)

    def get_max(k):
        i = k + offset
        ret = data[i]
        while i:
            if i % 2 == 0:
                ret = max(ret, data[i - 1])
            i = (i - 1) // 2
        return ret

    srt = sorted((h, i) for i, h in enumerate(hhh))
    for h, i in srt:
        update(i, get_max(i) + aaa[i])

    return data[0]


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))+[0]*(k+10)
inf=float("inf")
dp=[(inf) for i in range(n+k+10)]
dp[0]=0
#;print(dp)

for i in range(n-1):
    #print(i)
    for j in range(k):
        dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
    #print(dp,i)
print(dp[n-1])

### FIXED CODE ###

def main():
  n,k=map(int,input().split())
  h=list(map(int,input().split()))+[0]*(k+10)
  dp=[(float("inf")) for i in range(n+k+10)]
  dp[0]=0
  for i in range(n-1):
    for j in range(k):
      dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
  return (dp[n-1])
print(main())
### BUGGY CODE ###

N,M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

stim_A = [0]
for ind,i in enumerate(A):
    stim_A.append((stim_A[-1]+i)%M)

ans = 0
for ind,i in enumerate(stim_A[1:]):
    ans += 1 if i==0 else 0
    ans += stim_A[1:ind+1].count(i)
print(ans)

### FIXED CODE ###

N,M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]

stim_A = [0]
di = {}
ans = 0
for i in A:
    stim_A.append((stim_A[-1]+i)%M)
    if(stim_A[-1] in di):
        di[stim_A[-1]] += 1
    else:
        di[stim_A[-1]] = 1
for i in di:
    if(i==0):
        ans+=di[0]
    if(di[i]>1):
        ans += (di[i]-1)*di[i]//2
    
print(ans)
### BUGGY CODE ###

def comb(n,k,p):
  from math import factorial
  if n<0 or k<0 or n<k:return 0
  if n==0 and k==0:return 1
  a=factorial(n)%p
  b=factorial(k)%p
  c=factorial(n-k)%p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
  if b==0:
    return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return (d*d)%p
  else:
    return (a*power_func(a,b-1,p))%p
n,m=map(int,input().split())
mod=10**9+7
d=[]
for i in range(2,int(m**0.5)+1):
  if m%i==0:
    cnt=0
    while m%i==0:
      m//=i
      cnt+=1
    d.append(cnt)
if m>1:
  d.append(1)
ans=1
for k in d:
  ans=(ans*comb(k+n-1,k,mod))%mod
print(ans)

### FIXED CODE ###

from math import sqrt, floor
from collections import defaultdict
def comb(n,m):
    if m == 0:
        return 1
    return comb(n-1,m-1)*n // m
def facts(n):
    dic = defaultdict(int)
    for i in range(2,floor(sqrt(n))+1):
        while n % i == 0:
            n //= i
            dic[i] += 1
        if n == 1:
            break
    if n != 1:
        dic[n] += 1
    return dic
N, M = map(int,input().split())
mod = 10**9+7
ans = 1
dic = facts(M)
for p in dic:
    ans = (ans*(comb(dic[p]+N-1, dic[p]) % mod)) % mod
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(0, N-1):
    for j in range(i+1, N):
        ans += A[i]*A[j]

print(ans % 1000000007)

### FIXED CODE ###

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

ans = 0
tmp = 0
for i in range(N-2, -1, -1):
    tmp += A[i+1]
    ans += A[i] * tmp

print(ans % 1000000007)
### BUGGY CODE ###

n=int(input())
s=input()
dp=[[[0]*1000 for _ in range(4)] for _ in range(n+1)]
dp[0][0][0]=1
for i in range(n):
  n=int(s[i])
  for j in range(3):
    for k in range(100):
      dp[i+1][j+1][k*10+n]=max(dp[i+1][j+1][k*10+n],dp[i][j][k])
  for j in range(4):
    for k in range(1000):
      dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k])
ans=0
for i in range(1000):
  if dp[-1][3][i]==1:
    ans+=1
print(ans)

### FIXED CODE ###

import bisect

n=int(input())
s=input()
fpos=[-1]*10
npos=[[-1] for _ in range(10)]
for i in range(n):
  if fpos[int(s[i])]==-1:
    fpos[int(s[i])]=i
  npos[int(s[i])].append(i)
lpos=[len(npos[i]) for i in range(10)]
ans=0
for i in range(10):
  if fpos[i]==-1:
    continue
  for j in range(10):
    spos=bisect.bisect_right(npos[j],fpos[i])
    if spos>=lpos[j]:
      continue
    spos=npos[j][spos]
    for k in range(10):
      tpos=bisect.bisect_right(npos[k],spos)
      if tpos>=lpos[k]:
        continue
      ans+=1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)
def resolve():
    s = input()
    K = int(input())
    mem = []
    kinds = list(set(s))
    skips = []
    if len(kinds) > K:
        skips = kinds[K+1:]
    for j in range(len(s)): # window starts at
        if s[j] in skips:
            continue
        for i in range(1, len(s)+1): # window size
            subs = s[j:j+i]
            if subs not in mem:
                mem.append(subs)
    mem.sort()
    # print(mem)
    print(mem[K-1])


if '__main__' == __name__:
    resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
def resolve():
    s = input()
    K = int(input())
    mem = []
    for i in range(1, K+1): # window size
        for j in range(len(s)): # window starts at
            subs = s[j:j+i]
            if subs not in mem:
                mem.append(subs)
    mem.sort()
    # print(mem)
    print(mem[K-1])
    
    
if '__main__' == __name__:
    resolve()
### BUGGY CODE ###

n,t = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab0 = []
ab1 = []
for i in range(n):
  if ab[i][0] == 0:
    ab0.append(ab[i][1])
  else:
    ab1.append(ab[i])
ab0.sort()
ab1.sort(key = lambda x:x[0]/(x[1]+1),reverse=True)
n = len(ab1)
INF = float("inf")
dp = [[INF for i in range(31)] for j in range(n+1)]
for i in range(n+1):
  dp[i][0] = 0
for i in range(1,n+1):
  a,b = ab1[i-1]
  for j in range(1,31):
    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+1+a*(dp[i-1][j-1]+1)+b)
m = len(ab0)
ans = 0
for j in range(31):
  if dp[n][j] > t:
    continue
  anstmp = j
  ttmp = t-dp[n][j]
  i = 0
  while i <= m-1 and ttmp >= ab0[i]+1:
    ttmp -= ab0[i]+1
    anstmp += 1
    i += 1
  ans = max(ans,anstmp)
print(ans)

### FIXED CODE ###

n,t = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n)]
ab0 = []
ab1 = []
for i in range(n):
  if ab[i][0] == 0:
    ab0.append(ab[i][1])
  else:
    ab1.append(ab[i])
ab0.sort()
ab1.sort(key = lambda x:x[0]/(x[1]+1),reverse=True)
n = len(ab1)
dp = [[10**10 for i in range(31)] for j in range(n+1)]
for i in range(n+1):
  dp[i][0] = 0
for i in range(1,n+1):
  a,b = ab1[i-1]
  for j in range(1,31):
    dp[i][j] = min(dp[i-1][j],dp[i-1][j-1]+1+a*(dp[i-1][j-1]+1)+b)
m = len(ab0)
ans = 0
for j in range(31):
  if dp[n][j] > t:
    continue
  anstmp = j
  ttmp = t-dp[n][j]
  i = 0
  while i <= m-1 and ttmp >= ab0[i]+1:
    ttmp -= ab0[i]+1
    anstmp += 1
    i += 1
  ans = max(ans,anstmp)
print(ans)