Harryxun/stf_run huggingface dataset:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]

ablst=[[0]*w for i in range(h)]
ma=0
for i in range(h):
    for j in range(w):
        ablst[i][j]=abs(a[i][j]-b[i][j])
        ma=max(ma,ablst[i][j])
lst1=[0]*ma*(h*w+10)

lst=[[lst1[:] for i in range(w)] for i in range(h)]
lst[0][0][abs(a[0][0]-b[0][0])]=1


# print(lst)
for i in range(h):
    for j in range(w):
        if i+1<h:
            for k in range(len(lst[i][j])):
                if lst[i][j][k]==1:
                    lst[i+1][j][k+ablst[i+1][j]]=1
                    lst[i+1][j][abs(k-ablst[i+1][j])]=1
        if j+1<w:
             for k in range(len(lst[i][j])):
                if lst[i][j][k]==1:
                    lst[i][j+1][k+ablst[i][j+1]]=1
                    lst[i][j+1][abs(k-ablst[i][j+1])]=1
    # print(d)
        # print(lst[i][j])
# anslst=list(lst[-1][-1].keys())
# anslst.sort(key=lambda x: abs(x))
# print(lst)
for i in range(len(lst[-1][-1])):
    if lst[-1][-1][i]==1:
        print(i)
        break

### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline

h, w = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
# print(kouho)
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) % 2:
        print(i)
        exit()
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,c = m()

time = [[0 for i in range(31)] for j in range(10**5+1)]

for i in range(n):
    s,t,c = m()
    if time[s-1][c] == 0:
        time[t][c] = 1
        time[s][0] += 1    
        time[t+1][0] -= 1

    else:
        time[t][c] = 1
        time[s][0] += 1
        time[t+1][0] -= 1

ma = time[0][0]
for i in range(1,10**5+1):
    time[i][0] += time[i-1][0]
    ma = max(ma,time[i][0])
print(ma)




### FIXED CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,c = m()

time = [[0 for i in range(31)] for j in range(10**5+2)]

popopo = [[] for i in range(30)]

for i in range(n):
    s,t,c = m()
    popopo[c-1].append([s,t])


for i in range(30):
    popopo[i].sort()
    
for i in range(30):
    for j in range(len(popopo[i])):
        s,t = popopo[i][j]
        if time[s][i+1] == 0:
            time[t][i+1] = 1
            time[s-1][0] += 1
            time[t][0] -= 1
        else:
            time[t][i+1] = 1
            time[s][0] += 1
            time[t][0] -= 1

ma = time[0][0]
for i in range(1,10**5+2):
    time[i][0] += time[i-1][0]
    ma = max(ma,time[i][0])
print(ma)
while 1:
     x, y = map(int, raw_input().split())
     if x == 0 and y == 0:
         break
     if x > y:
         print '%s %s' % (y,x)
     else:
         print '%s %s' % (x,y)
    

### FIXED CODE ###

while 1:
   x, y = map(int, raw_input().split())
   if x == 0 and y == 0:
      break
   elif x > y:
      print '%s %s' % (y,x)
   else:
      print '%s %s' % (x,y)
N = int(input())

strs = []
dicts = {}
for i in range(N):
    s = input()
    if dicts.get(s) is not None:
        dicts[s] += 1
    else:
        dicts[s] = 1

dict_sorted = sorted(dict.items(), key=lambda x:x[1])

i = 0
for s in dict_sorted.key():
    if dicts[s] >= i:
        print(s)
    i = dicts[s]

### FIXED CODE ###

N = int(input())

strs = []
dicts = {}
for i in range(N):
    s = input()
    if dicts.get(s) is not None:
        dicts[s] += 1
    else:
        dicts[s] = 1

dict_sorted = sorted(dicts.items(), key=lambda x:x[1], reverse=True)

i = 0
sts = []
for s in dict_sorted:
    if dicts[s[0]] == dicts[dict_sorted[0][0]]:
        sts.append(s[0])
    i = dicts[s[0]]

for s in sorted(sts):
    print(s)
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
lst1 = [list(map(int,readline().split())) for i in range(n)]

from scipy.sparse.csgraph import shortest_path,floyd_warshall
from scipy.sparse import csr_matrix
lc = csr_matrix(lst1)
st = shortest_path(lc,method="FW")
ans = 0
for i in range(n):
    for j in range(i+1,n):
        if lst1[i][j] > st[i][j]:
            print(-1)
            exit()
        elif lst1[i][j]==st[i][j]:
            #他に最短距離がある場合はcontinue
            res = [0]*n
            for k in range(n):
                res[k] += lst1[i][k] + lst1[j][k]
            res[i] = -1
            res[j] = -1
            if any([res[k]==lst1[i][j] for k in range(n)]):
                continue
            else:
                ans += lst1[i][j]
        else:
            ans += lst1[i][j]

print(ans)

### FIXED CODE ###

import sys
from copy import deepcopy
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
lst1 = [list(map(int,readline().split())) for i in range(n)]

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d
st = deepcopy(lst1)
st = warshall_floyd(st)
ans = 0
for i in range(n):
    for j in range(i+1,n):
        if lst1[i][j] > st[i][j]:
            print(-1)
            exit()
        elif lst1[i][j]==st[i][j]:
            #他に最短距離がある場合はcontinue
            res = [0]*n
            for k in range(n):
                res[k] += lst1[i][k] + lst1[j][k]
            res[i] = -1
            res[j] = -1
            if any([res[k]==lst1[i][j] for k in range(n)]):
                continue
            else:
                ans += lst1[i][j]
        else:
            ans += lst1[i][j]

print(ans)
N, K = map(int, input().split())
S = list(input())
l = len(S)
X = []
cnt0 = 0
cnt1 = 0
for i in S:
    if i == '0':
        if cnt1 != 0:
            X.append(cnt1)
            cnt1 = 0
            cnt0 += 1
        else:
            cnt0 += 1
    else:
        if cnt0 != 0:
            X.append(cnt0)
            cnt0 = 0
            cnt1 += 1
        else:
            cnt1 += 1
if cnt1 != 0:
    X.append(cnt1)
elif cnt0 != 0:
    X.append(cnt0)
ans = []
if S[0] == '1': #Xの奇数は1
    sum0 = sum(X[0:2*K+1])
    ans.append(sum0)
    i = 1
    while 2*K+2*i-1 < len(X):
        ans.append(ans[i-1] + X[2*K+2*i-1] + X[2*K+2*i] - X[i] - X[i-1])
        i += 1
        print(ans)
else:
    sum0 = sum(X[0:2*K])
    ans.append(sum0)
    i = 1
    while 2*K+2*i < len(X):
        if i == 1:
            ans.append(ans[i-1] + X[2*K+2*i+1] + X[2*K+2*i] - X[i-1])
            i += 1
        else:
            ans.append(ans[i-1] + X[2*K+2*i+1] + X[2*K+2*i] + X[i] - X[i] - X[i-1])
            i += 1
print(max(ans))

### FIXED CODE ###

N, K = map(int, input().split())
S = list(input())
X = []
cnt = 1
for i in range(1, N):
    if S[i] != S[i-1]:
        X.append(cnt)
        cnt = 0
    cnt += 1
    if i == N-1:
        X.append(cnt)
l = len(X)

if S[0] == '0' and (l+1)//2 <= K:
    print(N)
    exit()
if S[0] ==  '1' and l//2 <= K:
    print(N)
    exit()

ans = 0
result = 0
if S[0] == '0':
    for j in range(2*K):
        result += X[j]
    ans = result
    for j in range(2*K, l):
        if j == 2*K:
            result -= X[0]
        elif j%2 == 0:
            result = result - X[j-2*K] - X[j-2*K-1]
        result += X[j]
        ans = max(ans,result)
else:
    for j in range(2*K+1):
        result += X[j]
    ans = result
    for j in range(2*K+1, l):
        if j%2 == 1:
            result = result - X[j-2*K-1] - X[j -2*K]
        result += X[j]
        ans = max(ans, result)
print(ans)
card_power = {'2':'0','2':'1','3':'2','4':'3','5':'4','6':'5','7':'6','8':'7','9':'8','10':'9','11':'10','11':'12','13':'12','1':'13'}
A,B = input().split()
if int(card_power[A]) > int(card_power[B]):
  print('Alice')
elif int(card_power[A]) < int(card_power[B]):
  print('Bob')
else:
  print('Draw')


### FIXED CODE ###

card_power = {'2':'1','3':'2','4':'3','5':'4','6':'5','7':'6','8':'7','9':'8','10':'9','11':'10','12':'11','13':'12',"1":'13'}
A,B = input().split()
if int(card_power[A]) == int(card_power[B]):
  print('Draw')
elif int(card_power[A]) > int(card_power[B]):
  print('Alice')
elif int(card_power[A]) < int(card_power[B]):
  print('Bob')
A = input()
B = input()

m = max(A, B)
m = m + m +1

print(m)

### FIXED CODE ###

A, B = (int(x) for x in input().split())

if A == B:
	print(A+B)
else :
	m = max(A, B)
	m = m*2 - 1
	print(m)
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

A, B = map(int, input().split(" "))

print(lcm(A, B))

### FIXED CODE ###

import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

A, B = map(int, input().split(" "))

print(lcm(A, B))
a = int,input()
print(a+a**2+a**3)

### FIXED CODE ###

a = input()
b = int(a)
print(b+b**2+b**3)
#   AtCoder Beginner Contest 119
#   problem A: Still TBD

S = input() #-> yyyy/mm/dd

date = S.split('/')

year = int(date[0])
month = int(date[1])
day = int(date[2])

if month >= 5:
    print('TBD')
elif
    print('Heisei')


### FIXED CODE ###

#   AtCoder Beginner Contest 119
#   problem A: Still TBD

S = input() #-> yyyy/mm/dd

date = S.split('/')

year = int(date[0])
month = int(date[1])
day = int(date[2])

if month >= 5:
    print('TBD')
else:
    print('Heisei')
a=input()
s=str(a)
if(s[-1] in ('2','4','5','7','9')):
	print('hon')
elif(s[-1] in ('0','1','6','8')):
	print('pon')
elif(s[-1] in 3):
	print('bonn')

### FIXED CODE ###

a=input()
s = str(a)
if(s[-1] in ('2','4','5','7','9')):
	print('hon')
elif(s[-1] in ('0','1','6','8')):
	print('pon')
elif(s[-1] == '3'):
	print('bon')
inp=list(map(int,input().split()))
S=inp[0]
B=inp[1]
R=inp[2]
x=S//(B+R)#brグループが何回
y=S%(B+R)

print(B*x+min(y,B))

### FIXED CODE ###

inp=input()
if inp=='AAA'or inp=='BBB':
  print('No')
else:
  print('Yes')
import math
a, b, c ,d = map(int, input().split())
e = (c * d) // math.gcd(c, d)
wareru = (int(b/c) + int(b/d) - int(b/e) - (int((a-1)/c) + int((a-1)/d) - int((a-1)/e)))
print(b-a+1-wareru)

### FIXED CODE ###

a, b, c ,d = map(int, input().split())
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
      return a*b//gcd(a,b)
e = lcm(c, d)
wareru = b//c + b//d - b//e - ((a-1)//c + (a-1)//d - (a-1)//e)
print(b-a+1-wareru)
n,m,k = map(int,input().split())
ans = 0
MOD = 10**9+7
for i in range(1,n):
    ans += i*(n-i)*(m**2)
for i in range(1,m):
    ans += i*(m-i)*(n**2)
from scipy.misc import comb
print((ans*comb(m*n-2,k-2,exact=True))%MOD)

### FIXED CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
dict = {}
for i in range(n):
    if a[i] not in dict:
        dict[a[i]] = 0
    dict[a[i]] += 1
for _ in range(m):
    b,c = map(int,input().split())
    if c not in dict:
        dict[c] = 0
    dict[c] += b
keys = list(dict.keys())
keys = sorted(keys)[::-1]
ans = 0
cnt = 0
for i in range(len(keys)):
    if n-cnt<=dict[keys[i]]:
        ans += keys[i] * (n-cnt)
        break
    else:
        ans += keys[i] * dict[keys[i]]
        cnt += dict[keys[i]]
print(ans)
class UnionFind:
  def __init__(self, n):
    self.parents = list(range(n))
    self.ranks = [1 for _ in range(n)]
  def parent(self, x):
    if x == self.parents[x]:
      return x
    else:
      p = self.parent(self.parents[x])
      self.parents[x] = p
      return p
  def union(self, x, y):
    host = x if self.ranks[x] < self.ranks[y] else y
    guest = x+y-host
    self.ranks[host] += self.ranks[guest]
    self.parents[self.parent(guest)] = host
  def find(self, x, y):
    return self.parent(x)==self.parent(y)
  def numtrees(self):
    return len(set(self.parents))

N, M = map(int, input().split())
E = []
for _ in range(M):
  a, b = map(int, input().split())
  E.append((a-1, b-1))
ans = 0
r = 0
while r < N:
  uf = UnionFind(N)
  i = 0
  while i < M:
    if i != r:
      a, b = E[i]
      uf.union(a, b)
    i += 1
  i = 0
  while i < N:
    _ = uf.parent(i)
    i += 1
  if uf.numtrees() > 1:
    ans += 1
  r += 1
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
E = []
for _ in range(M):
  a, b = map(int, input().split())
  E.append((a-1, b-1))
ans = 0
r = 0
while r < M:
  uf = UnionFind(N)
  i = 0
  while i < M:
    if i != r:
      a, b = E[i]
      uf.union(a, b)
    i += 1
  i = 0
  while i < N:
    _ = uf.find(i)
    i += 1
  if uf.group_count() > 1:
    ans += 1
  r += 1
print(ans)
K = int(input())

def calc_n(K):
  for n in range(1, int(K/2)+2):
    if n*(n+1)/2 == K:
      return n
  return "NO"

N = calc_n(K)
if not isinstance(N, int):
  print(N)
print(N+1)
all_num = {i:2 for i in range(1, K+1)}
remain = K * 2
#print(all_num)
pair = []
for i in range(1, K+1):
  if all_num[i] == 2:
    pair.append(i)
    all_num[i] -= 1
    remain -= 1
    if len(pair) == N:
      break
print(N, " ".join([str(i) for i in pair]))

while remain != N:
  pair = []
  for i in range(1, K+1):
    if all_num[i] == 1 and len(pair) == 0:
      pair.append(i)
      all_num[i] -= 1
      remain -= 1
    if all_num[i] == 2 and len(pair) != 0:
      pair.append(i)
      all_num[i] -= 1
      remain -= 1
      if len(pair) == N:
        break
  print(N, " ".join([str(i) for i in pair]))

pair = []
for i in range(1, K+1):
  if all_num[i] == 1:
    pair.append(i)
    all_num[i] -= 1
    remain -= 1
    if len(pair) == N:
      break
print(N, " ".join([str(i) for i in pair]))

### FIXED CODE ###

K = int(input())

def calc_n(K):
  for n in range(1, int(K/2)+2):
    if n*(n+1)/2 == K:
      return n
  return "No"

N = calc_n(K)
if not isinstance(N, int):
  print(N)
else:
  print("Yes")
  print(N+1)
  last = [i for i in range(1, N+1)]
  count = 2
  first_set = [str(i) if i == 1 else str(sum(last[:i-1])+1) for i in range(1, N+1)]
  print(N, " ".join(first_set))
  last_set = [str(sum(last[:i])) for i in range(1,N+1)]
  print(N, " ".join(last_set))
  while count != N+1:
    first_number = sum(last[:count-1])+1
    other_set = [i for i in range(first_number, first_number+count)]
    other_set.extend([first_number+count*(i+1)-1+sum(last[:i-1]) for i in range(1, N-count+1)])
    count += 1
    other_set = [str(i) for i in other_set]
    print(N, " ".join(other_set))
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def solve(positions, s, t):
    # print('{}, s = {}, t = {}'.format(positions, s, t))
    if len(t) == 0:
        return 0

    if len(positions[t[0]]) == 0:
        return -1

    i = 0
    j = 0
    while i < len(s) and j < len(t):
        candidates = positions[t[j]]
        pos = bisect.bisect_left(candidates, i)
        if pos == len(candidates):
            print('{} {}'.format(t[j], pos))
            break

        i = candidates[pos] + 1
        j += 1

    if j == len(t):
        return i
    else:
        rest = solve(positions, s, t[j:])
        return len(s) + rest if rest != -1 else -1


def main():
    s = input()
    t = input()

    positions = defaultdict(list)
    for i in range(len(s)):
        positions[s[i]].append(i)

    print(solve(positions, s, t))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def solve(positions, s, t):

    if not set(t) <= set(s):
        return -1

    loop = 0
    prev = -1

    for tchar in t:
        candidates = positions[tchar]
        pos = bisect.bisect_right(candidates, prev)

        if pos == len(candidates):
            loop += 1
            pos = 0
        prev = candidates[pos]

    return loop * len(s) + prev + 1


def main():
    s = input()
    t = input()

    positions = defaultdict(list)
    for i in range(len(s)):
        positions[s[i]].append(i)

    print(solve(positions, s, t))


if __name__ == '__main__':
    main()
import bisect

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = []
for i in range(M):
  B,C = map(int,input().split())
  BC.append([B,C])
BC.sort(key = lambda val: val[1], reverse = True)
#print(A)
#print(BC)

ans = 0
j = 0
count = BC[j][0]
for i in range(N):
  #print(ans)
  if A[i] < BC[j][1]:
    ans += BC[j][1]
    count -= 1
    if count == 0:
      j += 1
      count = BC[j][0]
      if j >= M:
        break
  else:
    break
if i < N:
  ans += sum(A[i:])
print(ans)


### FIXED CODE ###

import bisect

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
BC = []
for i in range(M):
  B,C = map(int,input().split())
  BC.append([B,C])
BC.sort(key = lambda val: val[1], reverse = True)
#print(A)
#print(BC)

ans = 0
j = 0
count = BC[j][0]
for i in range(N):
  #print(ans)
  if A[i] < BC[j][1]:
    ans += BC[j][1]
    count -= 1
    if count == 0:
      j += 1
      if j >= M:
        if i < N-1:
          ans += sum(A[i+1:])
        break
      count = BC[j][0]
  else:
    ans += sum(A[i:])
    break
print(ans)
# Widespread
n,a,b = list(map(int, input().split()))
h = []
for i in range(n):
    h.append(int(input()))

# やり直し
import math as m

def check(ary, num, a, b):
    bommed = [(hi- b*num) for hi in h if (hi- b*num)>0]
    acnt = sum([m.ceil(hi/(a-b)) for hi in bommed])
    if acnt > num:
        return "NO"
    else:
        return "YES"

imin = 1
imax = m.ceil(max(nh)/a)

while ( imax > imin+1 ):
    imid = imin + (imax-imin)//2
    if ( check(h, imid, imin, imax)=="YES" ):
        imax = imid
    else:
        imin = imid
print(imax)

### FIXED CODE ###

n,a,b = list(map(int, input().split()))
h = []
for i in range(n):
    h.append(int(input()))

import math

sup = sum([hh // a + 1 for hh in h])
inf = 1
 
while sup - inf > 1:
    x = (sup + inf) // 2
    c = sum([math.ceil((hh - x * b)/(a-b)) for hh in h if hh > x * b])
    if c <= x:
        sup = x
    else:
        inf = x
 
print(sup)
a, b=int(input())
if b%a==0:
  print(a+b)
else:
  print(b-a)

### FIXED CODE ###

a, b=map(int, input().split())
if b%a==0:
  print(a+b)
else:
  print(b-a)
N=int(input())
P = list(map(int,input().split()))
ans=0
m=P[0]

for i in P:
	if m >= i:
    	ans += 1
   		m = i
print(ans)

### FIXED CODE ###

N=int(input())
P = list(map(int,input().split()))
ans=0
m=P[0]
 
for i in range(N):
    if m >= P[i]:
        ans += 1
        m = P[i]

print(ans)
a,b,x,y,r = map(int,input().split())
if (x+r)>w or (y+r)>h or (x-r)<0 or (y-r)<0:
    print('No')
else:
    print('Yes')



### FIXED CODE ###

a,b,x,y,r = map(int,input().split())
if (x+r)>a or (y+r)>b or (x-r)<0 or (y-r)<0:
    print('No')
else:
    print('Yes')
n = input()
                                                                                                            def slv():
    a = ['a', 'e', 'i', 'o', 'u']
                                                                                                                for i in a:
        if i == n:
            print('vowel')
            return
    print('consonant')
                                                                                                            slv()

### FIXED CODE ###

n = input()

def slv():
    a = ['a', 'e', 'i', 'o', 'u']

    for i in a:
        if i == n:
            print('vowel')
            return
    print('consonant')

slv()
n = int(input())
piles = [int(x) for x in input().split()]
dp = [[0] * n for _ in range(n)]
for l in range(n-1,-1,-1):
    for r in range(l, n):
        if l == r:
            dp[l][r] = piles[l]
        else:
            dp[l][r] = max(piles[l] - dp[l+1][r], piles[r] - dp[l][r-1])
return dp[0][n-1]

### FIXED CODE ###

def deque(n, arr):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = arr[i]

    for l in range(n-2, -1, -1):
        for r in range(l+1, n):
            L = arr[l] - dp[l+1][r]
            R = arr[r] - dp[l][r-1]
            dp[l][r] = L if L > R else R
    return dp[0][n-1]

n = int(input())
arr = [int(x) for x in input().split()]
print(deque(n, arr))