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

n = int(input())
A = []
for i in range(n):
  s = input()
  A.append(sorted(s))
x = 0
for i in range(n):
	for j in range(i+1, n):
		if A[i] == A[j]:
			x+=1

print(x)

### FIXED CODE ###

n = int(input())
from collections import defaultdict as dd

hsh = dd(int)

for i in range(n):
  s = list(input())
  s = ''.join(sorted(s))
  hsh[s] += 1

x = 0
for i in hsh.keys():
  x += (hsh[i]*(hsh[i]-1))//2

print(x)
### BUGGY CODE ###

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

if k>=b-a:
    for i in range(a, b+1):
        print(i)

else:
    
    l1=[i for i in range(a,b+1)] 
    l2=[]
    for i in range(k):
        l2.append(l1[i])
    for i in range(b-a-k+1,b-a+1):
        l2.append(l1[i])

    l_set = list(set(l2))
    l_set.sort()
    for i in range(len(l_set)):
        print(l_set[i])

### FIXED CODE ###

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

ans=list(range(a,min(a+k,b)))+list(range(max(a,b-k+1),b+1))
ans=set(ans)
ans=list(ans)
ans.sort()
for i in range(len(ans)):
    print(ans[i])
### BUGGY CODE ###

X, K, D = map(int, input().split())

if abs(X) <= D * K:
    for i in range(K):
        a = abs(X) - (D * (i + 1))
        b = abs(X) - (D * i)
        if a < 0:
            break
    if abs(a) < abs(b):
        c = K - (i + 1)
        if c % 2 == 0:
            if 0 <= X:
                goal = a
            else:
                goal = -a
        else:
            if 0 <= X:
                goal = b
            else:
                goal = -b

    if abs(b) <= abs(a):
        c = K - i
        if c % 2 == 0:
            if 0 <= X:
                goal = b
            else:
                goal = -b
        else:
            if 0 <= X:
                goal = a
            else:
                goal = -a
else:
    if 0 <= X:
        goal = X - D * K
    else:
        goal = X + D * K

print(abs(goal))

### FIXED CODE ###

X, K, D = map(int, input().split())

if abs(X) < (K * D):
    a = abs(X) % D
    b = abs(D - a)
    c = abs(X) // D + 1
    if (K - c) % 2 == 0:
        goal = b
    else:
        goal = a
else:
    goal = abs(X) - ( D * K )

print(goal)
### BUGGY CODE ###

from operator import itemgetter

n, k = map(int, input().split())
td = [tuple(int(x) for x in input().split()) for _ in range(n)]

a = sorted(td, key=itemgetter(1), reverse=True)

ans = [0]
s = []
t = []
for i in range(k):
    ans[0] += a[i][1]
    if a[i][0] not in s:
        s.append(a[i][0])
    else:
        t.append(a[i][1])

p = len(s)
q = len(t) - 1

if q < 0:
    print(ans[0] + k * k)
    exit()

v = []
for i in range(k, n):
    if a[i][0] not in s:
        s.append(a[i][0])
        v.append(a[i][1])

ans[0] += p * p
d = 0

for x in v:
    ans.append(ans[d] + x - t[q] + (p + 1) * (p + 1) - p * p)
    p += 1
    d += 1
    q -= 1
    if q < 0:
        break

print(max(ans))

### FIXED CODE ###

from operator import itemgetter

n, k = map(int, input().split())
td = [tuple(int(x) for x in input().split()) for _ in range(n)]

a = sorted(td, key=itemgetter(1), reverse=True)

ans = [0]
s = set()
t = []
for i in range(k):
    ans[0] += a[i][1]
    if a[i][0] not in s:
        s.add(a[i][0])
    else:
        t.append(a[i][1])

p = len(s)
q = len(t) - 1

if q < 0:
    print(ans[0] + k * k)
    exit()

v = []
for i in range(k, n):
    if a[i][0] not in s:
        s.add(a[i][0])
        v.append(a[i][1])

ans[0] += p * p
d = 0

for x in v:
    ans.append(ans[d] + x - t[q] + (p + 1) * (p + 1) - p * p)
    p += 1
    d += 1
    q -= 1
    if q < 0:
        break

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

n = int(input())
li = list(map(int, input().split()))
ans_li = []
for i in range(1, n+1):
    ans_li.append(li.index(i)+1)
print(*ans_li)

### FIXED CODE ###

n = int(input())
li = list(map(int, input().split()))
ans_li = [0] * n
for i in range(n):
    ans_li[li[i]-1] = i+1
print(*ans_li)
### BUGGY CODE ###

import re
N,Q=map(int,input().split())
S=input()
list1=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
    str1=S[list1[i][0]-1:list1[i][1]]
    list2=re.findall("AC",str1)
    print(len(list2))
    


### FIXED CODE ###

import re
N,Q=map(int,input().split())
S=input()
t=[0]*(N+1)
for i in range(N):
    t[i+1]=t[i]+(1 if S[i:i+2]=="AC" else 0)
for i in range(Q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import sys
n=int(input())
lst=[]
for i in range(n):
  x,y,h=map(int,input().split())
  lst.append([x,y,h])
  
for j in range(101):
  for k in range(101):
    for i in range(n):
      H=abs(j-lst[i][0])+abs(k-lst[i][1])+lst[i][2]
      if H>0:
        if all(max(H-abs(j-lst[l][0])-abs(k-lst[l][1]),0)==lst[l][2] for l in range(n)):
          print(j,k,H)
          sys.exit()
        
  
  


### FIXED CODE ###

import sys
n=int(input())
lst=[]
for i in range(n):
  x,y,h=map(int,input().split())
  lst.append([x,y,h])
  
for j in range(101):
  for k in range(101):
    for i in range(n):
      H=abs(j-lst[i][0])+abs(k-lst[i][1])+lst[i][2]
      if H>0:
        if all(max(H-abs(j-lst[l][0])-abs(k-lst[l][1]),0)==lst[l][2] for l in range(n)):
          print(j,k,H)
          sys.exit()
### BUGGY CODE ###

from math import factorial
mod=10*9+7

def comb(a,r):
  return factorial(a) / factorial(r) / factorial(a - r)%mod

n,a,b=map(int,input().split())
ans=((pow(2,n)-1)%(10**9+7)-comb(n,a)-comb(n,b))
print(int(ans))

### FIXED CODE ###

mod=10**9+7
n,a,b=map(int,input().split())
ans=pow(2,n,mod)-1 #n種類の花を使って花束を作る総数は2^n-1通り
comb1=1 #nCaの計算
for i in range(n-a+1,n+1): #n*(n-1)*…*(n-a+1)を計算
 comb1*=i
 comb1%=mod
for i in range(1,a+1): #1/a!=1/(1*2*…*a)=1^(p-2)*2^(p-2)*…*a^(p-2) (p=10**9+7)を計算
 comb1*=pow(i,mod-2,mod)
 comb1%=mod
comb2=1
for i in range(n-b+1,n+1): #n*(n-1)*…*(n-b+1)を計算
 comb2*=i
 comb2%=mod
for i in range(1,b+1): #1/b!=1/(1*2*…*b)=1^(p-2)*2^(p-2)*…*b^(p-2) (p=10**9+7)を計算
 comb2*=pow(i,mod-2,mod)
 comb2%=mod
ans-=(comb1+comb2) #nCa、nCbを総数から引く
ans%=mod
print(ans)
### BUGGY CODE ###

n, k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort(reverse=True)

seed = max(h)
for i in range(0,n-k+1):
    high = max(h[i:i+k]) - min(h[i:i+k])
    if seed > high:
        seed = high

print(seed)

### FIXED CODE ###

n, k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort(reverse=True)

seed = h[0]
for i in range(0,n-k+1):
    high = h[i] - h[i+k-1]
    seed = min(high,seed)

print(seed)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for i in range(Q)]

def calc(A):
    ans = 0
    for i in range(len(A)):
        ans += A[i] * (i + 1)

    return ans

VALUE = [0 for i in range(100000)]

for i in range(N):
    VALUE[A[i] - 1] += 1

for i in range(Q):
    VALUE[BC[i][1] - 1] += VALUE[BC[i][0] - 1]
    VALUE[BC[i][0] - 1] = 0
    print(calc(VALUE))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [list(map(int, input().split())) for i in range(Q)]

def calc(A):
    ans = 0
    for i in range(len(A)):
        ans += A[i] * (i + 1)

    return ans

VALUE = [0 for i in range(100000)]

for i in range(N):
    VALUE[A[i] - 1] += 1

ANS = []
ANS.append(calc(VALUE))

for i in range(Q):
    VALUE[BC[i][1] - 1] += VALUE[BC[i][0] - 1]
    ANS.append(ANS[i] + (BC[i][1] - BC[i][0]) * VALUE[BC[i][0] - 1])
    VALUE[BC[i][0] - 1] = 0

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

n,m=map(int,input().split())
a=[]
b=[0]*(n+1)
b[1]=1
b[0]=1
MOD=(10**9)+7

for i in range(0,m):
  a.append(int(input()))
  
if 1 in a:
  b[1]=0
else:
  b[1]=1
  
for j in range(2,n+1):
  if j in a:
    continue
  else:
    b[j]=(b[j-1]+b[j-2])%MOD
    
print(b[n]%MOD)    
    
  
  
  



### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7
a=[0]*(n+1)
dp=[0]*(n+1)
dp[0]=1
for i in range(m):
    a[int(input())]=1
    
if a[1]==1:
    dp[1]=0
else:
    dp[1]=1
    
for j in range(2,n+1):
    if a[j]==0:
        dp[j]=dp[j-1]+dp[j-2] 
                  
print(dp[n]%mod)
### BUGGY CODE ###

from collections import defaultdict
N, M = map(int, input().split())
PY = []
PYd = defaultdict(list)
for i in range(M):
    x, y = map(int, input().split())
    PYd[x].append(y)
    PY.append((x,y))

for i in PYd.keys():
    PYd[i].sort()

for p,y in PY:
    str_p = str(p).zfill(6)
    index = str(1 + PYd[p].index(y)).zfill(6)
    print(str_p + index)

### FIXED CODE ###

from collections import defaultdict
import bisect
N, M = map(int, input().split())
PY = []
PYd = defaultdict(list)
for i in range(M):
    x, y = map(int, input().split())
    PYd[x].append(y)
    PY.append((x,y))

for i in PYd.keys():
    PYd[i].sort()

for p,y in PY:
    str_p = str(p).zfill(6)
    index = str(bisect.bisect(PYd[p],y)).zfill(6)
    print(str_p + index)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[list(map(int,input().split())) for i in range(Q)]
from bisect import bisect_left,bisect_right
# def 二分探索(リスト, 要素)
def index(lst, e):
    # Step 1. bisect_left して
    i = bisect_left(lst, e)
    
    # Step 2. 変な値を ValueError で弾いて
    if i == len(lst):
        return -1
    if lst[i] != e:
        return -1
    # Step 3. 値を返す。
    return i
def index2(lst, e):
    # Step 1. bisect_left して
    i = bisect_right(lst, e)
    
    # Step 2. 変な値を ValueError で弾いて
    if i == len(lst)+1:
        return -1
    if lst[i-1] != e:
        return -1
    # Step 3. 値を返す。
    return i

A=sorted(A)

for i in B:
    j=index(A,i[0])
    if not j==-1:
        k=index2(A,i[0])
        for l in range(j,k):
            A[l]=i[1]
    A=sorted(A)
    print(sum(A))


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[list(map(int,input().split())) for i in range(Q)]

dp=[0 for i in range(1,10**6)]
for i in A:
    dp[i]+=1
S=sum(A)
for i in B:
    S+=(i[1]-i[0])*dp[i[0]]
    print(S)
    dp[i[1]]+=dp[i[0]]
    dp[i[0]]=0
### BUGGY CODE ###

s=input()
n=len(s)
mod=10**9+7
dp=[[0 for i in range(13)] for j in range(n)]
if s[0]=='?':
    dp[0]=[1,1,1,1,1,1,1,1,1,1,0,0,0]
else:
    dp[0][int(s[0])]=1
for i in range(1,n):
    if s[i]!='?':
        for j in range(13):
            dp[i][(10*j+int(s[i]))%13]+=dp[i-1][j]
    else:
        for j in range(13):
            for k in range(10):
                dp[i][(10*j+k)%13]+=dp[i-1][j]
print(dp[n-1][5]%mod)

### FIXED CODE ###

s=input()
n=len(s)
mod=10**9+7
dp=[[0 for i in range(13)] for i in range(n)]
if s[0]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(s[0])]=1
for i in range(1,n):
  if s[i]=="?":
    for j in range(13):
      for k in range(10):
        dp[i][(10*j+k)%13]+=dp[i-1][j]
  else:
    for j in range(13):
      dp[i][(10*j+int(s[i]))%13]+=dp[i-1][j]
  for j in range(13):
    dp[i][j]%=mod
print(dp[n-1][5])
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
g = [[] for _ in range(n)]
inv = [0] * n
for i in range(n - 1 + m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    inv[b - 1] += 1
for i in range(n):
    if inv[i] == 0:
        q = deque([i])
        break
ans = [0] * n
while q:
    d = q.popleft()
    for node in g[d]:
        ans[node] = d + 1
        q.append(node)
for x in ans:
    print(x)


### FIXED CODE ###

n, m = map(int, input().split())
g = [[] for _ in range(n)]
inv = [0] * n
for _ in range(n - 1 + m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    inv[b - 1] += 1
for i in range(n):
    if inv[i] == 0:
        root = i
        break
d = [0] * n
s = [root]
while s:
    p = s.pop()
    for node in g[p]:
        inv[node] -= 1
        if inv[node] == 0:
            d[node] = max(d[node], d[p] + 1)
            s.append(node)
ans = [0] * n
for i in range(n):
    for node in g[i]:
        if d[node] == d[i] + 1:
            ans[node] = i + 1
for x in ans:
    print(x)
### BUGGY CODE ###

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

import numpy as np
dp = [0 for i in range(N)]

# 初期化
dp[0] = 0; 
# dp[1] = np.abs(A[1] - A[0]);

for i in range(1,N):
  lim = min(i,K)
  tmp = [dp[i-k] + np.abs(A[i] - A[i-k]) 
         for k in range(lim,0,-1)]
  dp[i] = min(tmp)
  
print(dp[-1])

### FIXED CODE ###

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

dp = [float('inf') for i in range(N)]

# 初期化
dp[0] = 0; 

for i in range(1,N):
  lim = min(i,K);
  for k in range(lim,0,-1):
    dp[i] = min(dp[i], dp[i-k] + abs(A[i]-A[i-k]))  
print(dp[-1])
### BUGGY CODE ###

a,b,c,d = map(int,input().split())

dp = [[1 for i in range(d+1)] for j in range(c+1)]
dp[0][0] = 0

mod = 10**9+7
#print(dp)
for i in range(1,c+1):
    for j in range(1,d+1):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod

ans = 0
for i in range(a,c+1):
    for j in range(b,d+1):
        ans += dp[i][j]
        ans %=mod
        #print(dp[i+1][j+1])
#print(dp)
print(ans%mod)

### FIXED CODE ###

p = 10 ** 9 + 7 # mod
N = (10 ** 6) * 2 + 10  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

def cmb(r, n, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

a = list(map(int,input().split()))
ans = cmb(a[2]+1,a[2]+a[3]+2,p) - cmb(a[1],a[2]+a[1]+1,p) - cmb(a[0],a[3]+a[0]+1,p) + cmb(a[0],a[0]+a[1],p)
print(ans%p)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)
N = int(input())
A = list(map(int,input().split()))
s = [0]*N
for i in range(N):
    s[i] = s[i-2]+A[i]

def f(n):
    if n==0:
        return 0
    elif n ==1:
        return max(A[0],A[1])
    elif n==2:
        return max(A[0],A[1],A[2])
    elif n%2==1:
        return max(A[n]+f(n-2),s[n-1])
    else:
        return max(A[n]+f(n-2),A[n-1]+f(n-3),s[n-2])

ans = f(N-1)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
s = [0]*N
for i in range(N):
    s[i] = s[i-2]+A[i]

dp = [0]*N
dp[1] = max(A[0],A[1])
if N>=3:
    dp[2] = max(A[0],A[1],A[2])
for n in range(3,N):
    if n%2==1:
        dp[n] = max(A[n]+dp[n-2],s[n-1])
    else:
        dp[n] = max(A[n]+dp[n-2],A[n-1]+dp[n-3],s[n-2])

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

s=input()
t=input()
n,m=len(s),len(t)
dp=[[0]*(m+1) for i in range(n+1)]
dp[0][0]=1

for i in range(n+1):
    for j in range(m+1):
        dp[i][j]=max(dp[i][j-1],dp[i-1][j])
        if i*j!=0 and s[i-1]==t[j-1]:
            dp[i][j]=max(dp[i-1][j-1]+1,dp[i][j])

ans=""
i,j=n,m
while 0<i and 0<j:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans+=s[i-1]
        i-=1
        j-=1

print(ans[::-1])





### FIXED CODE ###

s=input()
t=input()

dp=[[0 for j in range(len(t)+1)] for i in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i][j-1],dp[i-1][j])
            
i=len(s)
j=len(t)
ans=""

while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans=s[i-1]+ans
        i-=1
        j-=1
        
print(ans)
### BUGGY CODE ###

n = int(input())
d = []

for i in range(n):
    line = input().split()
    if line[0] == "insert":
        d.append(line[1])
    elif line[0] == "find":
        if line[1] in d:
            print("yes")
        else:
            print("no")

### FIXED CODE ###

n = int(input())
d = {}

for i in range(n):
    line = input().split()
    if line[0] == "insert":
        d[line[1]] = 1
    elif line[0] == "find":
        if line[1] in d:
            print("yes")
        else:
            print("no")
### BUGGY CODE ###

def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[[0]*4 for _ in [0]*c] for _ in [0]*r]
    dp[0][0][1] = d[0][0]
    for x in range(r):
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[x][y+1][z+1] = max(dp[x][y+1]
                                              [z+1], dp[x][y][z]+d[x][y+1])
                    dp[x][y+1][z] = max(dp[x][y+1][z], dp[x][y][z])
            if x != r-1:
                dp[x+1][y][1] = max(dp[x+1][y][1], max(dp[x][y])+d[x+1][y])
                dp[x+1][y][0] = max(dp[x+1][y][0], max(dp[x][y]))
    print(max(dp[r-1][c-1]))


main()


### FIXED CODE ###

def main():
    r, c, k = map(int, input().split())
    d = [[0]*c for _ in [0]*r]
    for _ in range(k):
        t1, t2, t3 = map(int, input().split())
        d[t1-1][t2-1] = t3
    dp = [[0]*4 for _ in [0]*c]
    dp[0][1] = d[0][0]
    for x in range(r):
        dp2 = [[0]*4 for _ in [0]*c]
        for y in range(c):
            for z in range(4):
                if y != c-1:
                    if z != 3:
                        dp[y+1][z+1] = max(dp[y+1]
                                           [z+1], dp[y][z]+d[x][y+1])
                    dp[y+1][z] = max(dp[y+1][z], dp[y][z])
            if x != r-1:
                dp2[y][1] = max(dp2[y][1],
                                max(dp[y])+d[x+1][y])
                dp2[y][0] = max(dp2[y][0], max(dp[y]))
        if x != r-1:
            dp = dp2
    print(max(dp[c-1]))


main()
### BUGGY CODE ###

import math

H,N=map(int,input().split())
A_list=[]
B_list=[]
for i in range(N):
    A,B=map(int,input().split())
    A_list.append(A)
    B_list.append(B)

amax=max(A_list)

inf=float('inf')
dp=[0]+[inf]*(H+amax)

for i in range(N):
    A=A_list[i]
    B=B_list[i]
    if A > H and B<dp[-1]:
        dp[-1]=B
        continue

    for j in range(A,1+H):
        if dp[j-A]+B<dp[j]:
            dp[j]=dp[j-A]+B
    
    minA=min(dp[H-A:])+B
    if minA < dp[-1]:
        dp[-1]=minA

print(dp[-1])


### FIXED CODE ###

import math

def main():
    H,N=map(int,input().split())

    inf=float('inf')
    dp=[0]+[inf]*H

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            #dp[-1]=min(B,dp[-1])
            if B < dp[-1]:
                dp[-1]=B
        else:
            for j in range(A,H+1):
                #dp[j]=min(dp[j-A]+B,dp[j])
                if dp[j-A]+B<dp[j]:
                    dp[j]=dp[j-A]+B

                if j > H-A:
                    #dp[-1]=min(dp[-1],dp[j]+B)
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print(dp[-1])

main()
### BUGGY CODE ###

N, K = map(int, input().split())
H = tuple(map(int, input().split()))

if K >= N:
    print(abs(H[0] - H[N-1]))
else:
    dp = [abs(H[0] - H[i]) for i in range(K)] + [0] * (N - K)
    for i in range(K, N):
        dp[i] = min([dp[i-j] + abs(H[i] - H[i-j]) for j in range(1, K+1)])

    print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = tuple(map(int, input().split()))

if K >= N:
    print(abs(H[0] - H[N-1]))
else:
    dp = [abs(H[0] - H[i]) for i in range(K)] + [10**9] * (N - K)

    for i in range(K, N):
        for j in range(1, K+1):
            dp[i]= min(dp[i], dp[i-j] + abs(H[i] - H[i-j]))

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

n, W = map(int, input().split())
w = []
v = []
for _ in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

# dp[i+1][j]=i番目までの品物から重さの総和がj以下となるように選んだ時の価値の総和の最大値
dp = [[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n):
    for j in range(W+1):
    # ナップザックの容量をjと仮定する
        # とi番目の品物を持てないとき
        if j < w[i]:
            # i番目の品物をスルーする
            dp[i + 1][j] = dp[i][j]
        # i番目の品物を持とうと思えば持てるとき
        else:
            # 1.i番目の品物を持たなかった場合
            # 2.i番目の品物を持った場合
            # 以上2通りの内、価値の総和が最大となる品物の選び方をする
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
print(dp[n][W])


# イメージはこんな感じ
# 入力が
# n = 4
# W = 5
# (w, v) = ((2, 3), (1, 2), (3, 4), (2, 2))
# となるとき
# → はナップザックに入ってる品物の重さ(j <= W)の総和
# ↓ はi(i <= n)番目までの品物を順に確認
# (i+1, j)は最初の品物を0番目として数えたときの、
# i番目までの品物から重さの総和がj以下となるように選んだ時の価値の総和の最大値
# i\j  0   1   2   3   4   5
#
#  0   0   0   0   0   0   0
#
#  1   0   0   3   3   3   3
#
#  2   0   2   3   5   5   5
#
#  3   0   2   3   5   6   7
#
#  4   0   2   3   5   6   7

### FIXED CODE ###

n, W = map(int, input().split())
w = []
v = []
for _ in range(n):
    ww, vv = map(int, input().split())
    w.append(ww)
    v.append(vv)

# dp[i+1][j]=i番目までの品物から重さの総和がj以下となるように選んだ時の価値の総和の最大値
dp = [[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n):
    for j in range(W+1):
    # ナップザックの容量をjと仮定する
        # とi番目の品物を持てないとき
        if j < w[i]:
            # i番目の品物をスルーする
            dp[i + 1][j] = dp[i][j]
        # i番目の品物を持とうと思えば持てるとき
        else:
            # 1.i番目の品物を持たなかった場合
            # 2.i番目の品物を持った場合
            # 以上2通りの内、価値の総和が最大となる品物の選び方をする
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
print(dp[n][W])


# イメージはこんな感じ
# 入力が
# n = 4
# W = 5
# (w, v) = ((2, 3), (1, 2), (3, 4), (2, 2))
# となるとき
# → はナップザックに入ってる品物の重さ(j <= W)の総和
# ↓ はi(i <= n)番目までの品物を順に確認
# (i+1, j)は最初の品物を0番目として数えたときの、
# i番目までの品物から重さの総和がj以下となるように選んだ時の価値の総和の最大値
# i\j  0   1   2   3   4   5
#
#  0   0   0   0   0   0   0
#
#  1   0   0   3   3   3   3
#
#  2   0   2   3   5   5   5
#
#  3   0   2   3   5   6   7
#
#  4   0   2   3   5   6   7
### BUGGY CODE ###

class Range_BIT:
    def __init__(self, n):
        self.n = n
        self.bit0 = [0]*(n+1)
        self.bit1 = [0]*(n+1)
    
    def _Add(self, k, x, is_bit0=True):
        if is_bit0 == True:
            data = self.bit0
        else:
            data = self.bit1
        while k <= self.n:
            data[k] += x
            k += k & -k
    
    def _Get(self, data, k):
        s = 0
        while k:
            s += data[k]
            k -= k&-k
        return s
    
    """ 配列の獲得 """
    def Array(self):
        array = [0]*(n+1)
        for i in range(self.n):
            array[i] = self.Get(i+1,i+2)
        return array[:-1]
    
    """ 区間[l:r)に対してxを加算 """
    def Add(self, l, r, x):
        self._Add(l, -x*(l-1), is_bit0=True)
        self._Add(r, x*(r-1), is_bit0=True)
        self._Add(l, x, is_bit0=False)
        self._Add(r, -x, is_bit0=False)
    
    """ 区間[l:r)の総和 """
    def Get(self, l, r):
        Pi = self._Get(self.bit1, r-1)*(r-1) - self._Get(self.bit1, l-1)*(l-1)
        Qi = self._Get(self.bit0, r-1) - self._Get(self.bit0, l-1)
        return Pi+Qi

n,a,b = map(int,input().split())
d = a-b
rbit = Range_BIT(n)
for i in range(n):
    h = int(input())
    rbit.Add(i+1, i+2, h)
ans = 0
while True:
  arr = rbit.Array()
  mx = max(arr)
  idx = arr.index(mx)
  if mx <= 0:
    break
  rbit.Add(1,n+1,-b)
  rbit.Add(idx+1, idx+2, -d)
  ans += 1
print(ans)

### FIXED CODE ###

import math
n,a,b = map(int,input().split())
H = list(int(input()) for _ in range(n))
l,r = 0, 10**9
d = a-b
while r-l>1:
    mid = (r+l)//2
    tmp = 0
    for h in H:
        if h <= mid*b:
            continue
        tmp += math.ceil((h-mid*b)/d)
    if tmp <= mid:
        r = mid
    else:
        l = mid
print(r)