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


N,K = map(int,input().split())
K += 1

AB = []

for i in range(N):

    a,b = map(int,input().split())
    AB.append([a,b])

kb = format(K,'b')
#print (kb)
ans = 0

for i in range(len(kb)):

    now = 0
    if kb[-1-i] == "1":

        for j in range(N):

            flag = True
            at = format(AB[j][0],'b')

            if len(kb) < len(at):
                continue

            for m in range(len(at)):

                

                if m == i and at[-1-m] == "1":
                    flag = False
                    break

                elif m > i and kb[-1-m] == "0" and at[-1-m] == "1":
                    flag = False
                    break

            if flag:
                now += AB[j][1]

        #print (i,now)
        ans = max(ans,now)
        
print (ans)


### FIXED CODE ###

N,K = map(int,input().split())
K += 1

AB = []

for i in range(N):

    a,b = map(int,input().split())
    AB.append([a,b,format(a,'b')])

kb = format(K,'b')
#print (kb)
ans = 0

for i in range(len(kb)):

    now = 0
    if kb[-1-i] == "1":

        for j in range(N):

            flag = True
            at = AB[j][2]

            if len(kb) < len(at):
                continue

            for m in range(len(at)):

                

                if m == i and at[-1-m] == "1":
                    flag = False
                    break

                elif m > i and kb[-1-m] == "0" and at[-1-m] == "1":
                    flag = False
                    break

            if flag:
                now += AB[j][1]

        #print (i,now)
        ans = max(ans,now)
        
print (ans)
### BUGGY CODE ###

n = int(input())
s = input()

R = []
G = []
B = []
for i in range(n):
    if(s[i] == 'R'):
        R.append(i)
    elif(s[i] == 'G'):
        G.append(i)
    else:
        B.append(i)

samu = 0

for i in R:
    for j in G:
        for k in B:
            X = sorted([i,j,k])
            if(X[2] - X[1] != X[1] - X[0]):
                samu += 1

print(samu)


### FIXED CODE ###

n = int(input())
s = input()

R = []
G = []
B = []
for i in range(n):
    if(s[i] == 'R'):
        R.append(i)
    elif(s[i] == 'G'):
        G.append(i)
    else:
        B.append(i)

samu = len(R) * len(G) * len(B)

for i in R:
    for j in G:
        k = int(2 * j - i)
        if(0 <= k < n):
            if(s[k] == 'B'):
                samu -= 1
        k = int(2 * i - j)
        if(0 <= k < n):
            if(s[k] == 'B'):
                samu -= 1
        if(i % 2 == j % 2):
            k = int((i + j) / 2)
            if(s[k] == 'B'):
                samu -= 1

print(samu)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
import sys
def gcd(a,b):
  if b==0:
    return a
  else:
    return gcd(b,a%b)

def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=gcd(ans,a[i])
  return ans



  


for i in range(n-1):
  for j in range(i+1,n):
    num=gcd(a[i],a[j])
    if num!=1:
      if setwise_coprime(a)==1:
        print("setwise coprime")
        sys.exit()
      else:
        print("not coprime")
        sys.exit()
print("pairwise coprime")

        












### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

#エラストテネスのふるい
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve

#高速素因数分解
def fast_factorization(n, sieve):
  prime={}
  while n>1:
    p=sieve[n]
    #nが素数の場合
    if p==0:
      prime[n]=prime.get(n,0)+1
      break
    #nが素数ではない場合
    else:
      prime[p]=prime.get(p,0)+1
      n=n//p
  return prime

check=set()
if setwise_coprime(a)==1:
  #素因数のダブリをcheck
  sieve=create_sieve(10**6)
  for i in range(n):
    if a[i]!=1:
      s=fast_factorization(a[i], sieve)
      for i in s:
        if i in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(i)
  print("pairwise coprime")    
else:
  print("not coprime")
### BUGGY CODE ###

N=int(input())
S=[input() for _ in range(N)]
S_set=list(set(S))

S_count=[S.count(w) for w in S_set]
S_vests=[S_set[i] for i in range(len(S_count)) if S_count[i]==max(S_count)]
S_vests.sort()
for i in range(len(S_vests)):
    print(S_vests[i])

### FIXED CODE ###

N=int(input())

d={}
for _ in range(N):
    S=input()
    if S in d:
        d[S]+=1
    else:
        d[S]=1
        
m=max(d.values())
for s in sorted(k for k in d if d[k]==m):
    print(s)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n = I()
al = list(MI())

ans = 1
for i in al:
    ans *= i

if ans > 10 ** 18:
    print("-1")
else:
    print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n = I()
a = list(MI())

if 0 in a:
    print("0")
    exit()
else:
    ans = 1
    for i in a:
        if i == 1:
            continue
        ans *= i
        if ans > 10 ** 18:
            print("-1")
            exit()

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

N,K = map(int,input().split())
a = list(map(int,input().split()))

ans = []
g = 0
for i in range(N-K+1):
  k = 1
  for s in range(K):
    k *= a[s+i]%10**9
  ans.append(k)
  if len(ans)>1:
    if ans[0]<ans[1]:
      print("Yes")
    else:
      print("No")
    del ans[0]


### FIXED CODE ###

N,K = map(int,input().split())
a = list(map(int,input().split()))


for i in range(N-K):
  if a[i]<a[i+K]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###


n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r * g * b


for i in range(n):
    for j in range(1, n // 2 + 1):
        if i-j < 0 or i+j > n-1:
            continue
        if s[i] != s[i-j] and s[i] != s[i+j] and s[i-j] != s[i+j]:
            ans -= 1
print(ans)



### FIXED CODE ###


n = int(input())
s = input()

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r * g * b


for i in range(n):
    for j in range(1, n // 2 + 1):
        if i-j < 0 or i+j > n-1:
            break
        if s[i] != s[i-j] and s[i] != s[i+j] and s[i-j] != s[i+j]:
            ans -= 1
print(ans)
### BUGGY CODE ###

import re

str = input()
k = int(input())

strl = list(set([c for c in str]))
strl.sort()

substring = []
for h in strl:
	compiled = re.compile(h)
	st = 0
	m = compiled.search(str, st)
	while m:
		sub = m.start()
		for i in range(sub, len(str)):
			t = str[sub:i+1]
			if(not (t in substring)):
				substring.append(t)
		st = sub + 1
		m = compiled.search(str, st)
	
	if(len(substring)-len(strl) >= k-1):
		break


substring.sort()
print(substring[k-1])

### FIXED CODE ###

import re

str = input()
k = int(input())

strl = list(set([c for c in str]))
strl.sort()

substring = []
for h in strl:
	compiled = re.compile(h)
	st = 0
	m = compiled.search(str, st)
	while m:
		sub = m.start()
		for i in range(sub, min(len(str), sub+5)):
			t = str[sub:i+1]
			if(not (t in substring)):
				substring.append(t)
		st = sub + 1
		m = compiled.search(str, st)
	
	if(len(substring)-len(strl) >= k-1):
		break


substring.sort()
print(substring[k-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    P=tuple(map(int1,input().split()))
    c=[[1]*N for _ in range(N)]
    ans=0
    dy,dx=[1,0,-1,0],[0,1,0,-1]
    prev_y,prev_x=-1,-1
    for p in P:
        que=deque([(p//N,p%N)])
        d=[[INF]*N for _ in range(N)]
        d[p//N][p%N]=0
        f=True
        while que and f:
            y,x=que.popleft()
            if y==prev_y and x==prev_x:
                tmp=d[y][x]+prev_d[prev_y][prev_x]
                break
            for k in range(4):
                ny,nx=(y+dy[k],x+dx[k])
                if 0<=ny<N and 0<=nx<N:
                    if d[ny][nx]==INF:
                        if c[ny][nx]==1:
                            d[ny][nx]=d[y][x]+1
                            que.append((ny,nx))
                        else:
                            d[ny][nx]=d[y][x]
                            que.appendleft((ny,nx))
                else:
                    tmp=d[y][x]
                    f=False
                    break
        ans+=tmp
        c[p//N][p%N]=0
        prev_d=[l[:] for l in d]
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
M=N**2
P=tuple(map(int1,input().split()))
d=[0]*M
for i in range(N):
    for j in range(N):
        d[i*N+j]=min(min(i,N-1-i),min(j,N-1-j))
used=[1]*M
ans=0
que=[]
for p in P:
    ans+=d[p]
    used[p]=0
    que.append(p)
    while que:
        x=que.pop()
        for ddx in (-1,1,-N,N):
            nx=x+ddx
            if 0<=nx<M:
                if used[x]==0 and d[nx]-d[x]>=1:
                    d[nx]-=1
                    que.append(nx)
                elif used[x]==1 and d[nx]-d[x]>=2:
                    d[nx]-=1
                    que.append(nx)
print(ans)
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))
p = 0
for n in range(N):
  for m in range(n+1, N):
    p += X[n]*X[m]
    if p >= 10**9 + 7:
      while p >= 10**9 + 7:
        p -= 10**9 + 7
      
print(p)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
p = 0
s = sum(X)
for n in range(N):
  s -= X[n] 
  s = s % (10**9 + 7)
  p += s * X[n]
  p = p % (10**9 + 7)

print(p)
### BUGGY CODE ###

import re
import sys
from collections import (
    Counter,
    defaultdict as ddict,
    deque,
    namedtuple as ntuple,
)
from functools import lru_cache
from heapq import *
from itertools import *
from pprint import pprint
from statistics import *
from string import (
    ascii_letters as letters,
    ascii_lowercase as ucletters,
    ascii_uppercase as lcletters,
    digits,
)

cache=lru_cache(None)

hexdigits=digits+'ABCDEFabcdef'

inf=float('inf')
int8_min=-128
int16_min=-32768
int32_min=-2147483648
int64_min=-9223372036854775808
int8_max=127
int16_max=32767
int32_max=2147483647
int64_max=9223372036854775807
uint8_max=255
uint16_max=65535
uint32_max=4294967295
uint64_max=18446744073709551615
ansmod=1000000007

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rl=lambda:next(sys.stdin)
rrs=lambda:list(map(str.strip,sys.stdin))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(map(list,rrs()))
rig=lambda:[[*map(int,x.split())] for x in rls()]

def nbs4(i,j):
    return [
                (i-1,j),
        (i,j-1),        (i,j+1),
                (i+1,j),
    ]

def nbs8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n

sys.setrecursionlimit(int32_max)

################################################

H,W=ris()
S=rg()

xs=[[0]*(W+1) for _ in range(H+1)]
ys=[[0]*(W+1) for _ in range(H+1)]
for i in range(H):
    for j in range(W):
        if S[i][j]!='#':
            if j==0:
                xs[i][j]=1
            else:
                xs[i][j]+=1+xs[i][j-1]
            if i==0:
                ys[i][j]=1
            else:
                ys[i][j]+=1+ys[i-1][j]

ans=0
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if xs[i][j]==0:
            continue
        if xs[i][j+1]:
            x=xs[i][j]=xs[i][j+1]
        else:
            x=xs[i][j]

        if ys[i+1][j]:
            y=ys[i][j]=ys[i+1][j]
        else:
            y=ys[i][j]

        if x+y-1>ans:
            ans=x+y-1

print(ans)


### FIXED CODE ###

import sys

H,W=map(int,next(sys.stdin).split())

xs=[[0]*(W+2) for _ in range(H+2)]
ys=[[0]*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    row=next(sys.stdin)
    for j in range(1,W+1):
        if row[j-1]!='.': continue
        xs[i][j]=1+xs[i][j-1]
        ys[i][j]=1+ys[i-1][j]

ans=0
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if xs[i][j]==0: continue
        x=xs[i][j]=max(xs[i][j],xs[i][j+1])
        y=ys[i][j]=max(ys[i][j],ys[i+1][j])
        ans=max(ans,x+y-1)

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

import sys 
sys.setrecursionlimit(100000000)
n = int(input())
graph = [[] for _ in range(n)]
color = [-1]*n
dist = [-1]*n
dist[0] = 0
visited = [0]*n
for _ in range(n-1):
  u, v, w = map(int, input().split())
  u -= 1
  v -= 1 
  graph[u] += [[v, w]]
  graph[v] += [[u, w]]
 
def dfs(u):
  visited[u] = 1
  if sum(visited) == n:
    return 
  for v, w in graph[u]:
    if dist[v] == -1:
      dist[v] = (dist[u] + w) % 2
      dfs(v)

dfs(0)
for i in dist:
  print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

global color 
global adlist
color = [0 for _ in range(100001)] 

def make_adlist(N, uvw):
  global adlist
  adlist = [[] for _ in range(N)]
  for u, v, w in uvw:
    adlist[u-1] += [[v-1, w%2]]
    adlist[v-1] += [[u-1, w%2]]
  return adlist 

def dfs(v, c):
  global color
  global adlist
  color[v] = c
  for next_v, w in adlist[v]:
    if color[next_v] != 0:
      continue
    if color[next_v] == 0 and w % 2 != 0:
      dfs(next_v, -c)
    elif color[next_v] == 0 and w % 2 == 0:
      dfs(next_v, c)

  return 


def main():
  N = int(input())
  uvw = [list(map(int, input().split())) for _ in range(N-1)]
  adlist = make_adlist(N, uvw)
  dfs(0, 1)
  for c in color[:N]:
    if c == 1:
      print(1)
    else:
      print(0)


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

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

ans = 0
for a, b in reversed(ab):
    while (a+ans) % b != 0:
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
ab = [list(map(int, input().split())) for _ in range(n)]

ans = 0
for a, b in reversed(ab):
    if (a + ans) % b != 0:
        ans += b - (a + ans) % b

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

import bisect
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
from operator import mul

import numpy as np
import re
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def comb(n, r):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :rtype: int
    """
    assert n >= r
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


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

max_comb = 0
ans = 0, 1
for a in A:
    def test(i):
        global max_comb, ans
        if 0 <= i < N and A[i] < a:
            c = comb(a, A[i])
            if c > max_comb:
                max_comb = c
                ans = a, A[i]

    # a /2 に近いほど大きい
    i = bisect.bisect_left(A, a / 2)
    test(i - 1)
    test(i)
    test(i + 1)
print(*ans)


### FIXED CODE ###

import bisect
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
from operator import mul

import numpy as np
import re
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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

# nCr を求める
# r が同じなら、n は大きいほうが nCr は大きい
n = A[-1]
# n が同じなら、r は n / 2 に近いほど大きい
r = bisect.bisect_left(A, n / 2)

if abs(A[r - 1] - n / 2) < abs(A[r] - n / 2):
    r -= 1
while A[r] == n:
    r -= 1
print(n, A[r])
### BUGGY CODE ###

#!/usr/bin/python3

import sys
import bisect
from collections import defaultdict

sys.setrecursionlimit(1000000)

n = int(input())
a = list(map(int, input().split()))

nbs = defaultdict(list)

for i in range(n - 1):
    (u, v) = map(int, input().split())
    nbs[u - 1].append(v - 1)
    nbs[v - 1].append(u - 1)


mlen =  [ 0 ] * n
dp = [ float('inf') ] * n

def getmlen(cur, p, ctail):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    idx = bisect.bisect_left(dp, ca)
    ov = dp[idx]

    ntail = ctail
    if ctail < idx:
        ntail = idx

    dp[idx] = ca
    mlen[cur] = ntail + 1
    
    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, ntail)

    dp[idx] = ov
    return



mlen[0] = 1
dp[0] = a[0]
for ch in nbs[0]:
    getmlen(ch, 0, 0)

for i in range(n):
    print(mlen[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
from bisect import bisect_left
 
N = int(input())
a = [int(i) for i in input().split()]
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  u, v = map(int, input().split())
  vec[u - 1].append(v - 1)
  vec[v - 1].append(u - 1)
 
lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis[pos] = v
 
dfs(0, -1)
 
ret[0] = 1
for i in range(N) :
  print(ret[i])
### BUGGY CODE ###

a=[]
i=1
k=1
l=0
rk=[]
bk=[]
a.append(int(input()))
for x in input().split(" "):
    a.append(int(x))

while k<=100000:
    while i<=a[0]:
        if a[i]>=k:
            rk.append(a[i])
        else:
            bk.append(a[i])
        i+=1
    if len(rk)==len(bk):
        l+=1
    rk=[]
    bk=[]
    i=1
    k+=1
        
print(l)

### FIXED CODE ###

n=0
a=[]
i=1
ii=1
l=0
tasu=0
rk=[]
bk=[]
n=int(input())
for x in input().split(" "):
    a.append(int(x))

a.sort()

print(a[int(len(a)/2)]-a[int(len(a)/2)-1])
### BUGGY CODE ###

N, M = map(int, input().split())
a = [j for j in range((2**N)+1) if j%2==0 and j>0]
b = [j for j in range((2**M)+1) if j%2==1]
A = a[:N]
B = b[:M]
c = A + B
l = []
num = 1
for i in range(len(c)-1):
    for j in range(num,len(c)):
        res = c[i] + c[j]
        l.append(res)
    num+=1

k=[]
for i in l:
    if i%2==0:
        k.append(i)
print(len(k))

### FIXED CODE ###

N, M = map(int, input().split())
a = []
b = []
if M == 0:
    for i in range(1,(2*N)+1):
        if i%2==0 and i>0:
            a.append(i)
elif N == 0:
    for i in range(1,(2*M)+1):
        if i%2==1:
            b.append(i)
else:
    for i in range(1,501):
        if i%2==0 and i>0:
            a.append(i)
        else:
            b.append(i)
c = a[:N] + b[:M]
l = []
num = 1
for i in range(len(c)-1):
    for j in range(num,len(c)):
        res = c[i] + c[j]
        l.append(res)
    num+=1

k=[i for i in l if i%2==0]
print(len(k))
### BUGGY CODE ###

from collections import defaultdict


def factorization(n):
    dict = defaultdict(int)
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            dict[i] = cnt

    if temp != 1:
        dict[temp] = 1

    if not dict:
        dict[n] = 1

    return dict


n = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

prime_factors = defaultdict(int)
factors = []

for a in A:
    a_factors = factorization(a)
    for prime, count in a_factors.items():
        prime_factors[prime] = max(count, prime_factors[prime])
    factors.append(a_factors)

B = []
for a, div_factors in zip(A, factors):
    num = 1
    for prime, count in prime_factors.items():
        dived_count = count - div_factors[prime]
        num *= prime ** dived_count
        num %= mod
    B.append(num)

print(sum(B)%mod)

### FIXED CODE ###

import fractions


mod = 10 ** 9 + 7

def lcm(a, b):
    return a * b // fractions.gcd(a, b)


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

num = 1
for a in A:
    num = lcm(num, a)

ans = 0
for a in A:
    ans += num // a
print(ans%mod)
### BUGGY CODE ###

word = input()
count = int(input())
reversed_flg = False

for i in range(count):
    line = input()
    if len(line) == 1:
        reversed_flg = not reversed_flg
    else:
        str_t, str_f, char = line.split()
        f = int(str_f)
        
        if (f == 1 and not reversed_flg) or (f == 2 and reversed_flg):
            word = char + word
        else:
            word = word + char

    if i == count - 1 and reversed_flg:
        word = word[::-1]

print(word) 

### FIXED CODE ###

word = input()
count = int(input())
reversed_flg = False
head = ''
tail = ''

for i in range(count):
    line = input()
    if len(line) == 1:
        reversed_flg = not reversed_flg
    else:
        str_t, str_f, char = line.split()
        f = int(str_f)

        if (f == 1 and not reversed_flg) or (f == 2 and reversed_flg):
            # word = char + word
            head = char + head
        else:
            # word = word + char
            tail += char

word = head + word + tail

if reversed_flg:
        word = word[::-1]

print(word)
### BUGGY CODE ###

n, a, b = map(int, input().split())
dp = [2 ** 60] * (n + 1)
dp[0] = 0
p = list(map(int, input().split()))
for i in range(n):
    dp[i + 1] = dp[0]
    dp[0] += a
    for j in range(i):
        if p[j] < p[i]:
            dp[i + 1] = min(dp[i + 1], dp[j + 1])
            dp[j + 1] += a
        else:
            dp[j + 1] += b
print(min(dp))

### FIXED CODE ###

n, a, b = map(int, input().split())
dp = [2 ** 60] * (n + 1)
dp[0] = 0
p = list(map(int, input().split()))
for i in range(n):
    dp[i + 1] = dp[0]
    dp[0] += a
    for j in range(i):
        if p[j] < p[i]:
            dp[i + 1] = min(dp[i + 1], dp[j + 1])
            dp[j + 1] += a
        else:
            dp[j + 1] += b
print(min(dp))
### BUGGY CODE ###

n,p=map(int,input().split());a=1
for i in range(2,int(p**(1./n))+1):
 while p%(i**n)<1:a*=i;p//=i**n
print(a)

### FIXED CODE ###

n,p=map(int,input().split());a=1
print(n<2and p or exec("for i in range(2,int(p**(1./n))+1):\n while p%(i**n)<1:a*=i;p//=i**n")or a)
### BUGGY CODE ###

import sys
from bisect import bisect_left, bisect, insort_left, insort
A = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        insort(A, int(s[7:]))
    elif s[2] == "t":
        S.append(A.pop())
    else:
        break
print("\n".join(map(str, S)))



### FIXED CODE ###

import sys
from heapq import heapify, heappush, heappop
hq = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        heappush(hq, -int(s[7:]))
    elif s[2] == "t":
        S.append(-heappop(hq))
    else:
        break
print("\n".join(map(str, S)))