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

# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    K, A, B = map(int, input().split())
    cnt = 0
    if B - A >= 3:
        times = (K - (A - 1)) // 2
        if times >= 1:
            cnt += A
            for i in range(times):
                temp= (cnt // A) * B
                temp2 =cnt % A
                cnt=temp+temp2
            if (K - (A - 1)) // 2 == (K - (A - 1)) / 2:
                pass
            else:
                cnt += 1
        else:
            cnt = 1 + K
    else:
        cnt = 1 + K

    print(cnt)


resolve()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    K, A, B = map(int, input().split())
    cnt = 0
    if B - A >= 3:
        times = (K - (A - 1)) // 2
        if times >= 1:
            cnt += A
            cnt+=(B-A)*times
            if (K - (A - 1)) // 2 == (K - (A - 1)) / 2:
                pass
            else:
                cnt += 1
        else:
            cnt = 1 + K
    else:
        cnt = 1 + K

    print(cnt)


resolve()
### BUGGY CODE ###

N, K = [int(v) for v in input().split()]

links = []
for k in range(K):
    L, R = [int(v) for v in input().split()]
    links.append((L, R))

links = sorted(links, key=lambda x: x[1])

count = [1]
sub = [0, 1]
subtotal = 1

for i in range(1, N):
    v = 0
    for l, r in links:
        r2 = i - l + 1
        l2 = i - r
        if l2 < 0:
            l2 = 0
        if r2 >= 0:
            v += sub[r2] - sub[l2]

    count.append(v % 998244353)
    subtotal += v
    sub.append(subtotal)

print(count[-1])


### FIXED CODE ###

N, K = [int(v) for v in input().split()]

links = []
for k in range(K):
    L, R = [int(v) for v in input().split()]
    links.append((L, R))

links = sorted(links, key=lambda x: x[1])

count = [1]
sub = [0, 1]
subtotal = 1

for i in range(1, N):
    v = 0
    for l, r in links:
        r2 = i - l + 1
        l2 = i - r
        if l2 < 0:
            l2 = 0
        if r2 >= 0:
            v += sub[r2] - sub[l2]

    count.append(v % 998244353)
    subtotal = (subtotal + v) % 998244353
    sub.append(subtotal )

print(count[-1])
### BUGGY CODE ###

n=int(input(''))
def e(x,y):
    z=1
    if x<y:
        z=x
        x=y
        y=z

    while x!=0 and y!=0 and z!=0 and x!=y:
        z=x%y
        x=y
        y=z
    return x

s=0
for a in range(n):
    for b in range(n):
        u=e(a+1,b+1)
        for c in range(n):
            v=e(b+1,c+1)
            w=e(u,v)
            s=s+w

print(s)

### FIXED CODE ###

n=int(input(''))
def e(x,y):
    z=1
    if x<y:
        z=x
        x=y
        y=z

    while x!=0 and y!=0 and z!=0 and x!=y:
        z=x%y
        x=y
        y=z
    return x

el=[]
for a in range(n):
    kara=[]
    for b in range(n):
        kara.append(e(a+1,b+1))
    
    el.append(kara)

s=0
for a in range(n):
    for b in range(n):
        u=el[a][b]
        for c in range(n):
            v=el[b][c]
            w=el[u-1][v-1]
            s=s+w

print(s)
### BUGGY CODE ###

from collections import Counter
s = input()
ac = [0]
for i in range(len(s)):
    char = s[i]
    digit = len(s) - i - 1
    ac.append((ac[-1] + (int(char) * 10**digit)) % 2019)
#print(ac)

C = Counter(ac)
#print(C)
ans = 0
for val in C.values():
    ans += val * (val - 1) // 2
print(ans)

### FIXED CODE ###

from collections import Counter
s = input()
ac = [0]

def power_func(a,b,p):
    """a^b mod p を求める"""
    if b==0: return 1
    if b%2==0:
        d=power_func(a,b//2,p)
        return d*d %p
    if b%2==1:
        return (a*power_func(a,b-1,p ))%p

for i in range(len(s)):
    char = s[i]
    digit = len(s) - i - 1
    ac.append((ac[-1] + (int(char) * power_func(10, digit, 2019))) % 2019)
#print(ac)

C = Counter(ac)
#print(C)
ans = 0
for val in C.values():
    ans += val * (val - 1) // 2
print(ans)
### BUGGY CODE ###

n, k = map(lambda x: int(x), input().split(" "))
Ps = list(map(lambda x: int(x), input().split(" ")))

result = 0
expected_list = []
for p in Ps:
    temp = (p * (p + 1) / 2 )/ p
    expected_list.append(temp)

for i in range(n-k+1):
    temp = expected_list[i:i+k]
    temp = sum(temp)
    result = max(result, temp)

print(result)

### FIXED CODE ###

n, k = map(lambda x: int(x), input().split(" "))
Ps = list(map(lambda x: int(x), input().split(" ")))

result = 0
expected_list = []
temp_result = 0
for i, p in enumerate(Ps):
    temp = (p * (p + 1) / 2 )/ p
    expected_list.append(temp)
    temp_result += temp
    if i+1 >= k:
        result = max(result, temp_result)
        temp_result -= expected_list[i-k+1]

print(result)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
def f(i):
  res=0
  t=2**i
  a_nex=sorted([p%(2*t) for p in a])
  b_nex=sorted([p%(2*t) for p in b])
  l=0
  p=q=r=0
  for k in reversed(a_nex):
    while p<N and k+b_nex[p]<t:
      p+=1
    while q<N and k+b_nex[q]<2*t:
      q+=1
    while r<N and k+b_nex[r]<3*t:
      r+=1
    l+=q-p+N-r
  res=(l%2)<<i
  return res
for k in range(29):
  ans+=f(k)
print(ans)   
  


### FIXED CODE ###

import numpy as np
bisect_left = np.searchsorted
N = input()
a = np.int32(input().split())
b = np.int32(input().split())
ans = 0
for k in range(29):
    low = pow(2, k)
    high = pow(2, k + 1)
    x = a % high
    y = b % high
    y.sort()
    y = np.hstack((y - high, y))  # 配列を横に連結
    left = bisect_left(y, low - x)
    right = bisect_left(y, high - x)
    if np.sum(right - left) % 2:
        ans += low
print(ans)
### BUGGY CODE ###

N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
for l in range(N):
  if xh[l][1]==0:
    #print(l)
    continue
  la = (xh[l][1]+A-1)//A
  xh[l][1]=0
  r=l
  for _ in range(N):
    if l<N and r<N and 2*D>xh[r][0]-xh[l][0]:
      if 2*D<abs(xh[l][0]-xh[min(r+1,N-1)][0]):
        break
      else:
        r+=1
        if r<N:
          xh[r][1]=max(0,xh[r][1]-la*A)
    else:
      break
  ans +=la
  if r==l:
    r+=1
print(ans)


### FIXED CODE ###

N,D,A=[int(x) for x in input().split()]
xh = [[int(x) for x in input().split()] for _ in range(N)]
xh = sorted(xh)
r=0
l=0
ans = 0
mi = 10**9
d = [0]*(N+1)
for l in range(N):
  if d[l]<xh[l][1]:
    la = (xh[l][1]-d[l]+A-1)//A
    for _ in range(N):
      if l<N and r<N and 2*D>=xh[r][0]-xh[l][0]:
        r+=1
      else:
        break
    ans += la
    d[l]+=la*A
    d[r]-=la*A
  d[l+1]+=d[l]
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if m==0:
    dp[1]=1
elif not broken[0]==1:
    dp[1]=1
for i in step:
    if not i in broken:
        dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[n])

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = {i: 0 for i in range(N+1)}
mod = 10 ** 9 + 7
for _ in range(M):
    A[int(input())] = 1
 
dp = [0 for _ in range(N+1)]
dp[0] = 1
 
for i in range(N+1):
    if A.get(i+1) == 0:
        dp[i + 1] += dp[i]
    if A.get(i+2) == 0:
        dp[i + 2] += dp[i]
 
print(dp[N]%mod)
### BUGGY CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
import sys
sys.setrecursionlimit(10**6)
mod=998244353
n=i1() 
d=[]
for i in range(n):
  d.append(i2())
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
r=[]
dt=[0 for i in range(n)]
dt[-1]=1
for i in range(n):
 r.append(bisect.bisect_left(dx,dx[i]+dd[i]))

def ddd(i):
  x=i
  for k in range(i+1,r[i]):
      if dt[k]==0:
         x=max(x,ddd(k))
      else:
         x=max(x,dt[k])
  dt[i]=x
  return x
for i in range(n)[::-1]:
    dt[i]=ddd(i)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]+=dp[dt[i]+1]
  dp[i]%=mod
print(dp[0])    

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)>>1
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d.sort()
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 tx=dx[i]+dd[i]
 j=bisect.bisect_left(dx,tx)
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])
### BUGGY CODE ###

S = str(input())
T = str(input())

for i in range(len(S)):
    if S[i] == T[i]:
        continue
    else:
        s_before = S[i]
        S = S.replace(T[i], ',')
        S = S.replace(S[i], T[i])
        S = S.replace(',', s_before)


if (S == T):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import string

alphabet = string.ascii_lowercase

S = str(input())
T = str(input())
start = [-1 for i in range(len(alphabet))]
goal = [-1 for i in range(len(alphabet))]
tf = True

for i in range(len(S)):
    a = alphabet.index(S[i])
    b = alphabet.index(T[i])

    if (start[a] != -1 or goal[b] != -1):
        if (start[a] != b or goal[b] != a):
            tf = False
            break
    else:
        start[a] = b
        goal[b] = a

if tf:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import deque


def dfs(rel, s):
    dist = [-1] * len(rel)

    q = deque()
    q.append(s)
    dist[s] = 0

    while len(q):
        e = q.popleft()
        for ei in Rel[e]:
            if dist[ei] >= 0:
                continue
            q.append(ei)
            dist[ei] = dist[e] + 1

    ans = [0] * (len(rel) - 1)
    for d in dist:
        ans[d] += 1
    return ans


N, X, Y = map(int, input().split())
Rel = [None] + [[] for _ in range(N)]
for i in range(1, N + 1):
    if i > 1:
        Rel[i].append(i - 1)
    if i < N:
        Rel[i].append(i + 1)
Rel[X].append(Y)
Rel[Y].append(X)

K = [0] * (N - 1)

for i in range(1, N + 1):
    dist = dfs(Rel, i)
    for k, v in enumerate(dist[1:]):
        K[k] += v

for k in K[:-1]:
    print(k // 2)
print(0)

### FIXED CODE ###

N, X, Y = map(int, input().split())
D = [None] + [0] * (N - 1)
for i in range(1, N):
    for j in range(i + 1, N + 1):
        d = min(abs(j - i),
                abs(X - i) + 1 + abs(j - Y),
                abs(Y - i) + 1 + abs(j - X))
        D[d] += 1

for d in D[1:]:
    print(d)
### BUGGY CODE ###

N = int(input())

A_list = list(map(int,input().split()))

for i in range(1,N+1):
  print(A_list.count(i))

### FIXED CODE ###

import collections

N = int(input())

A_list = list(map(int,input().split()))
c = collections.Counter(A_list)

for i in range(1,N+1):
  print(c[i])
### BUGGY CODE ###

n,m = list(map(int,input().split()))
uv = [[] for ni in range(n)]
for i in range(m):
  u,v = map(lambda x:int(x)-1,input().split())
  uv[u].append(v)
s,t = list(map(lambda x:int(x)-1,input().split()))
flag = 0
time = 0
a = [set() for ni in range(n)]
a[s].add(0)
while time < 3*n:
  time += 1
  ad = []
  for ni in range(n):
    ad.append(set(map(lambda x:x+1,a[ni])))
  for ni in range(n):
    luv = len(uv[ni])
    for luvi in range(luv):
      a[uv[ni][luvi]] |= ad[ni]
  for x in a[t]:
    if x%3 == 0:
      flag = 1
      ans = x//3
  if flag == 1:
    break
if flag==0:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
pst = [[] for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  pst[a].append(b)
s,t = map(int,input().split())
s -= 1
t -= 1
cnt = [[0,0,0] for _ in range(n)]
cnt[s][0] = 1
now = [s]
time = 0
while now:
  time += 1
  last = now
  now = []
  for x in last:
    for y in pst[x]:
      if cnt[y][time%3] == 0:
        cnt[y][time%3] = 1
        now.append(y)
  #print(time,cnt,now)
  if cnt[t][0] == 1:
    print(time//3)
    break
else:
  print(-1)
### BUGGY CODE ###

import collections

n = int(input())
v = list(map(str, input().split()))

f = collections.Counter([v[i] for i in range(n) if i % 2 == 0]).most_common()
s = collections.Counter([v[i] for i in range(n) if i % 2 == 1]).most_common()

ans = []

for i in f:
    for j in s:
        if i[0] == j[0]:
            pass
        else:
            ans.append(i[1] + j[1])

if ans:
    print(n - max(ans))
else:
    print(n // 2)


### FIXED CODE ###

from collections import Counter

n = int(input())
v = list(map(str, input().split()))

f = Counter(v[::2]).most_common(2)
s = Counter(v[1::2]).most_common(2)

if f[0][0] != s[0][0]:
    print(n - f[0][1] - s[0][1])
else:
    if len(f) == 1 or len(s) == 1:
        print(n // 2)
    else:
        print(n - max(f[0][1] + s[1][1], f[1][1] + s[0][1]))
### BUGGY CODE ###

n,k=map(int,input().split())
l=[0]
for _ in range(n):
    a,b=map(int,input().split())
    l+=[a]*b
l.sort()
print(l[k])

### FIXED CODE ###

n,k=map(int,input().split())
l=[0]*(10**5+1)
for _ in range(n):
    a,b=map(int,input().split())
    l[a]+=b
s=0    
for i in range(len(l)):
    s+=l[i]
    if s>=k:
        print(i)
        break
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


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


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def main():
    N, M, Q = read_values()
    T = [list(read_index()) for _ in range(M)]
    L0 = [0] * N
    R0 = [0] * N
    for i, (l, r) in enumerate(T):
        L0[r] += 1 << i
        R0[l] += 1 << i

    for i in range(1, N):
        L0[i] += L0[i - 1]
        R0[-i - 1] += R0[-i]

    for _ in range(Q):
        p, q = read_index()
        t = R0[p] & L0[q]
        print(bin(t).count("1"))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


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


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def main():
    N, M, Q = read_values()
    S = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
    
    for _ in range(M):
        l, r = read_values()
        S[l][r] += 1

    for l in range(N):
        for r in range(N):
            S[l + 1][r + 1] += S[l + 1][r] + S[l][r + 1] - S[l][r] 

    res = [0] * Q
    for i in range(Q):
        p, q = read_values()
        res[i] = str(S[q][q] - S[p - 1][q] - S[q][p - 1] + S[p - 1][p - 1])
    print("\n".join(res))


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

import copy
R, C, K = map(int,input().split())
i = [list(map(int,input().split())) for k in range(K)]
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = copy.deepcopy(dp0)
dp2 = copy.deepcopy(dp0)
dp3 = copy.deepcopy(dp0)
item = copy.deepcopy(dp0)
for k in range(K):
   item[i[k][0]-1][i[k][1]-1] = i[k][2]
for r in range(R):
   for c in range(C):
      dp3[r][c] = max(dp3[r][c], dp2[r][c] + item[r][c])
      dp2[r][c] = max(dp2[r][c], dp1[r][c] + item[r][c])
      dp1[r][c] = max(dp1[r][c], dp0[r][c] + item[r][c])
      dp1[r][c+1] = max(dp1[r][c], dp1[r][c+1])
      dp2[r][c+1] = max(dp2[r][c], dp2[r][c+1])
      dp3[r][c+1] = max(dp3[r][c], dp3[r][c+1])
      dp0[r+1][c] = max(dp0[r+1][c], dp1[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp2[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp3[r][c])
ans = max(dp0[R-1][C-1], dp1[R-1][C-1])
ans = max(ans, dp3[R-1][C-1])
ans = max(ans, dp2[R-1][C-1])
print(ans)

### FIXED CODE ###

import sys
import copy
R, C, K = map(int, input().split())
item = [[0] * (C + 1) for _ in range(R + 1)]  # dp配列と合わせるために, 0行目, 0列目を追加している.
for s in sys.stdin.readlines():
    r, c, v = map(int, s.split())
    r -= 1
    c -= 1
    item[r][c] = v
    
dp0 = [[0] * (C+1) for r in range(R+1)]
dp1 = [[0] * (C+1) for r in range(R+1)]
dp2 = [[0] * (C+1) for r in range(R+1)]
dp3 = [[0] * (C+1) for r in range(R+1)]
 
for r in range(R):
   for c in range(C):
      dp3[r][c] = max(dp3[r][c], dp2[r][c] + item[r][c])
      dp2[r][c] = max(dp2[r][c], dp1[r][c] + item[r][c])
      dp1[r][c] = max(dp1[r][c], dp0[r][c] + item[r][c])
      dp1[r][c+1] = max(dp1[r][c], dp1[r][c+1])
      dp2[r][c+1] = max(dp2[r][c], dp2[r][c+1])
      dp3[r][c+1] = max(dp3[r][c], dp3[r][c+1])
      dp0[r+1][c] = max(dp0[r+1][c], dp1[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp2[r][c])
      dp0[r+1][c] = max(dp0[r+1][c], dp3[r][c])
ans = max(dp0[R-1][C-1], dp1[R-1][C-1])
ans = max(ans, dp3[R-1][C-1])
ans = max(ans, dp2[R-1][C-1])
print(ans)
### BUGGY CODE ###



import collections

n = int(input())
a = list(map(int, input().split(" ")))
q = int(input())
have_map = collections.Counter(a)
for i in range(q):
    x, y = map(int, input().split(" "))
    have_map[y] = have_map.get(x, 0) + have_map.get(y, 0)
    have_map.pop(x, 0)

    cost = 0
    for k,v in have_map.items():
        cost += k * v
    print(cost)


### FIXED CODE ###



import collections

n = int(input())
a = list(map(int, input().split(" ")))
q = int(input())
have_map = collections.Counter(a)

total_cost = 0
for k,v in have_map.items():
    total_cost += k * v

for i in range(q):
    x, y = map(int, input().split(" "))
    if x in have_map:
        diff = have_map[x] * -x  + have_map[x] * y
        total_cost += diff

    have_map[y] = have_map.get(x, 0) + have_map.get(y, 0)
    have_map.pop(x, 0)

    print(total_cost)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    print(0)
    s = input().strip()
    seats = [''] * (N+1)
    seats[0], seats[-1] = s, s
    l, r = 0, N
    while s != 'Vacant':
        m = (l + r) // 2
        print(m)
        s = input().strip()
        if (m - l) % 2 == 0 and s != seats[l]:
            r = m
        elif (m - l) % 2 == 1 and s == seats[l]:
            r = m
        elif (r - m) % 2 == 0 and s != seats[r]:
            l = m
        elif (r - m) % 2 == 1 and s == seats[r]:
            l = m

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    print(0, flush=True)
    s = input().strip()
    if s == 'Vacant':
        return True
    ls, rs = s, s
    l, r = 0, N
    while True:
        m = (l + r) // 2
        print(m, flush=True)
        s = input().strip()
        if s == 'Vacant':
            return True
        if (m - l) % 2 == 0 and s != ls:
            r = m
            rs = s
        elif (m - l) % 2 == 1 and s == ls:
            r = m
            rs = s
        elif (r - m) % 2 == 0 and s != rs:
            l = m
            ls = s
        elif (r - m) % 2 == 1 and s == rs:
            l = m
            ls = s

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

from collections import defaultdict
from copy import copy

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

ms = [2,5,5,4,5,6,3,7,6]
dic = defaultdict(lambda: 0)
for a in A:
    dic[ms[a-1]] = max(dic[ms[a-1]], a)

sd = sorted(dic.items())

dp = [None] * (N+1)
dp[0] = defaultdict(lambda: 0)

for i in range(sd[0][0], N+1):
    cands = []
    for l,a in sd:
        if i-l < 0: break
        if dp[i-l] is None: continue
        cands.append(copy(dp[i-l]))
        cands[-1][a] += 1
    if not cands: continue
    max_v = 0
    max_j = -1
    for j,cand_dic in enumerate(cands):
        tmp_s = ''
        for a,n in sorted(cand_dic.items(), reverse=True):
            tmp_s += str(a) * n
        tmp_v = int(tmp_s)
        if tmp_v > max_v:
            max_v = tmp_v
            max_j = j
    dp[i] = cands[max_j]

ans = ''
for a,n in sorted(dp[-1].items(), reverse=True):
    ans += str(a) * n
print(ans)

### FIXED CODE ###

from collections import defaultdict
from copy import copy

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

ms = [2,5,5,4,5,6,3,7,6]
dic = defaultdict(lambda: 0)
for a in A:
    dic[ms[a-1]] = max(dic[ms[a-1]], a)

sd = sorted(dic.items())

dp = [None] * (N+1)
dp[0] = defaultdict(lambda: 0)

for i in range(sd[0][0], N+1):
    cands = []
    least_len = -1
    for l,a in sd:
        if i-l < 0: break
        if dp[i-l] is None: continue
        if cands and sum(dp[i-l].values())+1 < least_len:
            continue
        cands.append(copy(dp[i-l]))
        cands[-1][a] += 1
        least_len = sum(cands[-1].values())
    if not cands: continue
    max_v = 0
    max_j = -1
    for j,cand_dic in enumerate(cands):
        tmp_s = ''
        for a,n in sorted(cand_dic.items(), reverse=True):
            tmp_s += str(a) * n
        tmp_v = int(tmp_s)
        if tmp_v > max_v:
            max_v = tmp_v
            max_j = j
    dp[i] = cands[max_j]

ans = ''
for a,n in sorted(dp[-1].items(), reverse=True):
    ans += str(a) * n
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int, input().split()))
tester=True
for i in range(n):
    for j in range(i+1,n):  
        if l[i]==l[j]:
            tester=False
            break

if tester==True:
    print('YES')
else:
    print('NO')




### FIXED CODE ###

n=int(input())
l=list(map(int, input().split()))
s=set(l)
if len(l)==len(s):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import numpy as np
MOD = 10**9 + 7
n = int(input())
array = np.array([list(map(int, format(num, "060b")))[::-1] for num in map(int, input().split())], dtype="int64")
sum_ = 0
for idx, column in enumerate(array.T):
    n_ones = column.sum()
    sum_ += ((n_ones * (n - n_ones)) % MOD) * ((2 ** idx) % MOD) % MOD
    sum_ %= MOD
print(sum_)

### FIXED CODE ###

import numpy as np
MOD = 10**9 + 7
n = int(input())
A = np.array(list(map(int, input().split())))

answer = 0
for i in range(60):
    n_ones = np.count_nonzero(A & 1)
    answer += 2 ** i * (n - n_ones) * n_ones
    A >>= 1

print(answer % MOD)
### BUGGY CODE ###

N = int(input())
S = input()

Ans = 0
for i in range(N):
  s = S[i]
  a = 0
  b = 0
  L = ["R","G","B"]
  L.remove(s)
  for j in range(i+1,N):
    t = S[j]
    if s != t:
      if t == L[0]:
        a +=1
      else:
        b +=1
  Ans += a*b

for i in range(N):
  for j in range(i+1,N):
    s = S[i]
    t = S[j]
    k = 2*j-i
    if s != t and k <= N-1:
      u = S[k]
      if t != u and u != s:
        Ans -=1
print(Ans)

### FIXED CODE ###

N = int(input())
S = input()

L = [0,0,0]
for i in range(N):
    if S[i] == "R":
        L[0] +=1
    elif S[i] == "G":
        L[1] +=1
    else:
        L[2] +=1

Ans = L[0]*L[1]*L[2]

for i in range(N):
  s = S[i]
  n = min(N, (N+i)//2 + 1)
  for j in range(i+1,n):
    t = S[j]
    if s != t:
      k = 2*j-i
      if k <= N-1:
        u = S[k]
        if t != u and u != s:
          Ans -=1
print(Ans)
### BUGGY CODE ###

a, b, n = map(int, input().split())
ans = 0

for i in range(1, n + 1):
    num = (a * i) // b - a * (i // b)
    if ans < num:
        ans = num

print(ans)


### FIXED CODE ###

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

if b > n:
    x = n
else:
    x = b - 1

print((a * x) // b)