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

import numpy as np
N, A = map(int, input().split())
X = list(map(int, input().split()))

dp = np.zeros((N+1, N+1, 2555), np.int64)
dp[0][0][0] = 1
for i in range(N):
  for j in range(N):
    for k in range(2555):
      if dp[i][j][k] == 0: continue
      # not used
      dp[i+1][j][k] += dp[i][j][k]
      # used
      dp[i+1][j+1][k+X[i]] += dp[i][j][k]
ans = 0
for i in range(1, N+1):
  ans += dp[N][i][i*A]
print(ans)  

### FIXED CODE ###

N, A = map(int, input().split())
X = list(map(int, input().split()))
sum_X = sum(X)
dp = [[[0]*(sum_X+1) for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
  for j in range(N):
    for k in range(sum_X):
      if dp[i][j][k] == 0: continue
      # not used
      dp[i+1][j][k] += dp[i][j][k]
      # used
      dp[i+1][j+1][k+X[i]] += dp[i][j][k]
ans = 0
for k in range(1, N+1):
  if k*A <= sum_X:
    ans += dp[N][k][k*A]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = [int(i) for i in input().split()]

dp = [[0] * (N+1) for i in range(N+1)]

def func():
    for s in range(1, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
            else:
                dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
    
func()
print(dp[0][N])

### FIXED CODE ###

import sys
input = sys.stdin.readline

def func():
    N = int(input())
    A = [int(i) for i in input().split()]

    dp = [[0] * (N+1) for i in range(N+1)]
    if (N - 1) % 2 == 0:
        fl = 1
    else:
        fl = -1
    for i in range(N):
        dp[i][i+1] = fl * A[i]

    for s in range(2, N+1):
        for l in range(N-s+1):
            r = l + s
            if (N - s) % 2 == 0:
                dp[l][r] = max(dp[l+1][r]+A[l], dp[l][r-1]+A[r-1])
                continue
            dp[l][r] = min(dp[l+1][r]-A[l], dp[l][r-1]-A[r-1])
                
    return dp[0][N]

print(func())
### BUGGY CODE ###

n = int(input())

l = []

for i in range(n):
  l.append(int(input()))

m = max(l)

if l.count(m) >= 2:
  for i in range(n):
    print(m)
  exit()

for i in range(n):
  tmp = l.pop(i)
  
  if tmp != m:
    print(m)
    l.insert(i,tmp)
    continue
  
  print(max(l))
  l.insert(i,tmp)
  

### FIXED CODE ###

n = int(input())

l = []

for i in range(n):
  l.append(int(input()))

m = max(l)

if l.count(m) >= 2:
  for i in range(n):
    print(m)
  exit()

index = l.index(m)  

l.pop(index)

for i in range(n):
  if i == index:
  	print(max(l))
  else:
    print(m)
### BUGGY CODE ###

N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
group_id = {i:[] for i in range(1, N+1)}
group = {}
isChecked = [0] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
g = 0
for i in range(1, N+1):
    if isChecked[i]:
        continue
    isChecked[i] = 1
    isChecked[i] = 1
    group_id[i] = g
    x = [i]
    ch = child[i].copy()
    while ch:
        c = ch.pop(0)
        if isChecked[c]:
            continue
        group_id[c] = g
        isChecked[c] = 1
        x.append(c)
        ch = list(set(ch) | set(child[c]) - set(x))
    group[g] = len(x)
    g += 1

for i in range(1, N+1):
    ans[i] = group[group_id[i]] - len(child[i]) - 1

for _ in range(K):
    c, d = map(int, input().split())
    if group_id[c] == group_id[d]:
        ans[c] -= 1
        ans[d] -= 1
        
print(*ans[1:])

### FIXED CODE ###

N, M, K = map(int, input().split())
ans = [0] * (N + 1)
child = {i:[] for i in range(1, N+1)}
isChecked = [0] * (N + 1)
isBlocked = [set() for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    child[a].append(b)
    child[b].append(a)
    
for _ in range(K):
    c, d = map(int, input().split())
    isBlocked[c].add(d)
    isBlocked[d].add(c)
    
for i in range(1, N+1):
    if isChecked[i]:
        continue
    isChecked[i] = 1
    x = set([i])
    ch = child[i].copy()
    while ch:
        c = ch.pop()
        if isChecked[c]:
            continue
        isChecked[c] = 1
        x.add(c)
        ch.extend(child[c])
    for j in x:
        ans[j] = len(x) - 1 - len(child[j]) - len(x & isBlocked[j])
        
print(*ans[1:])
### BUGGY CODE ###

S = input()
N = len(S)
cnt = 0
while True:
  tmpcnt = 0
  for i in range(N-1):
    #print(S[N-2-i:N-i])
    if S[N-2-i:N-i] == 'BW':
      S = S[:N-2-i] + 'WB' + S[N-i:]
      #print(S)
      cnt += 1
      tmpcnt += 1
  if tmpcnt == 0:
    break
print(cnt)


### FIXED CODE ###

S = input()
N = len(S)
sum = 0
cnt = 0
for i in range(N):
  if S[i] == 'B':
    cnt += 1
  else:
    sum += cnt
print(sum)
### BUGGY CODE ###

def main():

    s = input()
    q = int(input())

    flag = 0
    query = []
    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s = q[2] + s
            else:
                s += q[2]
        else:
            if q[1] == "1":
                s += q[2]
            else:
                s = q[2] + s

    if flag % 2 == 1:
        print(s[::-1])
    else:
        print(s)

main()

### FIXED CODE ###

from collections import deque

def main():

    s = deque(input())
    q = int(input())

    flag = 0
    query = []

    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s.appendleft(q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.appendleft(q[2])

    if flag % 2 == 1:
        print("".join(list(s)[::-1]))
    else:
        print("".join(s))

main()
### BUGGY CODE ###

from collections import deque
while 1:
    c = input()
    r = input()
    if c == 0: break
    l = [map(int, raw_input().split()) for i in range(r)]
    ans = 0
    d = [(-1,0),(0,-1),(1,0),(0,1)]
    for i in range(c):
        for j in range(r):
            q = deque()
            a = [[0]*c for x in range(r)]
            if l[j][i] == 0: continue
            a[j][i] = 1
            q.append((j,i))
            while len(q) != 0:
                cy, cx = q.popleft()
                for x, y in d:
                    dx = x + cx; dy = y + cy;
                    if 0<=dx<c and 0<=dy<r and a[dy][dx] == 0 and l[dy][dx] == 1:
                        q.append((dy, dx))
                        a[dy][dx] = a[cy][cx] + 1
            for i in range(c):
                for j in range(r):
                    ans = max(ans, a[j][i])
    print ans

### FIXED CODE ###

while 1:
    c = input()
    r = input()
    if c == 0: break        
    l = [map(int, raw_input().split()) for i in range(r)]
    ans = 0
    d = [(-1,0),(0,-1),(1,0),(0,1)]
    def dfs(j, i, cnt):
        global ans
        ans = max(ans, cnt)
        for x, y in d:
            dx = x + i; dy = y + j
            if 0<=dx<c and 0<=dy<r and l[dy][dx]:
                l[dy][dx] = False
                dfs(dy, dx, cnt+1)
                l[dy][dx] = True
    for i in range(c):
        for j in range(r):
            if l[j][i]:
                l[j][i] = False
                dfs(j,i,1)
                l[j][i] = True
    print ans
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
A = []
cnt = 0

for i in range(n-1):
    A.append(a[i])
    if sum(A) > 0:
        while sum(A) + a[i+1] >= 0:
            a[i+1] -= 1
            cnt += 1

    elif sum(A) < 0:
        while sum(A) + a[i+1] <= 0:
            a[i+1] += 1
            cnt += 1

if sum(a) == 0:
    cnt += 1

print(cnt)

### FIXED CODE ###

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

def Chk(a, pos):
    cnt = 0
    tmp = 0

    for a in A:
        tmp += a

        if pos and tmp < 1:
            cnt += 1 - tmp
            tmp = 1
        elif not pos and tmp > -1:
            cnt += 1 + tmp
            tmp = -1

        pos = not pos
    return cnt

print(min(Chk(A, True), Chk(A, False)))
### BUGGY CODE ###

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

que=[[0,0,1]]
used={(0,0)}
bcount =0
for i in maplis:
    bcount+=i.count("#")


def check(x,y,c):
    f=(x<0 or x>w-1 or y<0 or y>h-1)
    f=(f or maplis[y][x]=="#")
    f=(f or (x,y) in used)
    if not f:
        que.append([x,y,c+1])

f=-1
while que:
    x,y,c=que.pop(0)
    if x==w-1 and y==h-1:
        f=c
        break
    used.add((x,y))
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))
    used.add((x,y))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))
### BUGGY CODE ###

def solve():
    N = int(input())
    s = input()
    ans = 0
    for i in range(1000):
        t = str(i).zfill(3)
        t_index = 0 
        for s_index in range(N):
            if s[s_index] == t[t_index]:
                t_index += 1
                if t_index == 3:
                    break
        if t_index == 3:
            ans += 1
    print(ans)
solve()

### FIXED CODE ###

def solve():
    ans = 1
    N = int(input())
    s = input()
    ans = 0
    for i in range(1000):
    	t = str(i).zfill(3)
    	t_index = 0 
    	for s_index in range(N):
    		if s[s_index] == t[t_index]:
    			t_index += 1
    			if t_index == 3:
    				break
    	if t_index == 3:
    		ans += 1
    print(ans)
solve()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
e=enumerate
def dfs(v):
  d=sorted(map(dfs,t[v]))
  l=len(d)
  return max([0]+[l-i+d for i,d in e(d)])
n,*a=map(int,open(0))
t=[[]for _ in[0]+a]
for i,v in e(a,1):t[v-1]+=i,
print(dfs(0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
e=enumerate
def dfs(v):
  d=sorted(map(dfs,t[v]))
  l=len(d)
  return max([0]+[l-i+d for i,d in e(d)])
n,*a=map(int,open(0))
t=[[]for _ in[0]+a]
for i,v in e(a,1):t[v-1]+=i,
print(dfs(0))
### BUGGY CODE ###

import math
import sys
r,g,b,n = map(int, input().split())
count=0
hiku=0
for i in range(n+1):
    for j in range(n+1):
        hiku=n-r*i-g*j
        if hiku%b==0 and hiku>=0:
            count+=1
print(count)

### FIXED CODE ###

import math
import sys
r,g,b,n = map(int, input().split())
count=0
hiku=0
for i in range(n+1):
    for j in range(n+1):
        hiku=n-r*i-g*j
        if hiku%b==0 and hiku>=0:
            count+=1
print(count)
### BUGGY CODE ###


# -*- coding: utf-8 -*-

import copy 
N, K, C=map(int, input().split())
s=list(input())


for i in range(N):
    if s[i]=='o':
        si=copy.copy(s)
        si[i]='x'
        day=N
        count=0
        flag=False
        while day>0 and count<K:
            if si[day-1]=='x':
                day-=1
            else:
                count+=1
                day-=C+1
                if count==K:
                    flag=True
        if flag==False:
            print(i+1)
            



### FIXED CODE ###


# -*- coding: utf-8 -*-

import numpy as np
N, K, C=map(int, input().split())
s=list(input())

forward=np.zeros(K)
back=np.zeros(K)

day=0
count=0
while day <N and count<K:
    if s[day]=='o':
        forward[count]=day
        count+=1
        day+=C+1
    else:
        day+=1

day=N-1
count=0
while day<N and count<K:
    if s[day]=='o':
        back[count]=day
        count+=1
        day-=C+1
    else:
        day-=1

#print(forward)
#print(back[::-1])

for i in range(K):
    if forward[i]==back[K-1-i]:
        print(int(forward[i])+1)
### BUGGY CODE ###

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

from fractions import gcd

if N == 2:
    print(max(A))
    exit()

ans = []
for n in range(N):
    if n == 0:
        x = A[1]
    else:
        x = A[0]

    for i, ai in enumerate(A):
        if i == n:
            continue
        x = gcd(x, ai)
    ans.append(x)

print(max(ans))

### FIXED CODE ###

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

from fractions import gcd

H = [A[0]]
x = A[0]
for i in range(1, N):
    x = gcd(x, A[i])
    H.append(x)


T = [A[-1]]
x = A[-1]
for i in range(2, N+1):
    x = gcd(x, A[-1 * i])
    T.append(x)

# print('H', H)
# print('T', T)

r = []
for i in range(N):
    if i == 0:
        ans = T[-2]
        r.append(ans)
    elif i == N - 1:
        ans = H[-2]
        r.append(ans)
    else:
        ans = gcd(H[i-1], T[N-i-2])
        r.append(ans)
print(max(r))
### BUGGY CODE ###

MOD=10**9+7
UPPERLIMIT=3*10**5
MODMUL=[1, 1]+[0]*(UPPERLIMIT-1)
for i in range(2, UPPERLIMIT+1):
  MODMUL[i]=MODMUL[i-1]*i%MOD
MODDIV=[1]*UPPERLIMIT+[pow(MODMUL[-1], MOD-2, MOD)]
for i in range(UPPERLIMIT, 0, -1):
  MODDIV[i-1]=MODDIV[i]*i%MOD
def MODCOMB(n, r):
  if n<r or n<1:
    return 0
  else:
    return (((MODMUL[n]*MODDIV[r])%MOD)*MODDIV[n-r])%MOD

N, M, K=map(int, input().split())

ans=0
k=MODCOMB(N*M-2, K-2)
for x1 in range(N-1):
  for x2 in range(x1+1, N):
    ans=(ans+abs(x1-x2)*M*M*k)%MOD
    
for y1 in range(M-1):
  for y2 in range(y1+1, M):
    ans=(ans+abs(y1-y2)*N*N*k)%MOD
    
print(ans)

### FIXED CODE ###

MOD=10**9+7
UPPERLIMIT=3*10**5
MODMUL=[1, 1]+[0]*(UPPERLIMIT-1)
for i in range(2, UPPERLIMIT+1):
  MODMUL[i]=MODMUL[i-1]*i%MOD
MODDIV=[1]*UPPERLIMIT+[pow(MODMUL[-1], MOD-2, MOD)]
for i in range(UPPERLIMIT, 0, -1):
  MODDIV[i-1]=MODDIV[i]*i%MOD
def MODCOMB(n, r):
  if n<r or n<1:
    return 0
  else:
    return (((MODMUL[n]*MODDIV[r])%MOD)*MODDIV[n-r])%MOD

N, M, K=map(int, input().split())

ans=0
k=MODCOMB(N*M-2, K-2)
for sa in range(1, N):
  ans=(ans+sa*(N-sa)*M*M*k)%MOD
    
for sa in range(1, M):
  ans=(ans+sa*(M-sa)*N*N*k)%MOD
    
print(ans)
### BUGGY CODE ###

import numpy as np
n=int(input())
for i in range(int(np.sqrt(n)),n+1):
    if np.sqrt(i)==int(np.sqrt(i)): a=i
print(a)

### FIXED CODE ###

import numpy as np
n=int(input())
for i in range(n,0,-1):
    if np.sqrt(i)==int(np.sqrt(i)):
        print(i)
        break
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
i = 0
cnt = 1
while a[i]!=2:
    if i == a[a[i]-1]-1:
        print(-1)
        exit()
    i=a[i]-1
    cnt += 1
else:
    print(cnt)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
cnt = 0
tmp = 0
for i in range(n):
    if a[tmp]==2:
        print(cnt+1)
        exit()
    else:
        tmp =a[tmp]-1
        cnt += 1
else:
    print(-1)
    exit()
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort()
a.reverse()
b.sort()
b.reverse()
c.sort()
c.reverse()
ans=[]
if x*y*z<=3000:
  p=x
  q=y
  r=z
else:
  p=min(x,3000)
  q=min(y,3000)
  r=min(z,3000)
for i in range(p):
  for j in range(q):
    for h in range(r):
      ans.append(a[i]+b[j]+c[h])
ans.sort()
ans.reverse()
for i in range(k):
  print(ans[i])

### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
ans2=[]
for i in range(x):
  for j in range(y):
    ans.append(a[i]+b[j])
if len(ans)>=k:
  ans.sort()
  ans.reverse()
  ans=ans[:k]
for i in range(len(ans)):
  for j in range(z):
    ans2.append(ans[i]+c[j])
ans2.sort()
ans2.reverse()
for i in range(k):
  print(ans2[i])
### BUGGY CODE ###

N = int(input())
X = input()
bin_X = int(X, 2)
cnt = 0
for i in X:
    if i == '1':
        cnt += 1

def bit_count(bits):
    cnt = 0
    while bits:
        bits = bits & (bits-1)
        bits >> 1
        cnt += 1
    return cnt


def pop_counter(n):
    return n % bit_count(n)


ans = 0
for n, i in enumerate(X):
    ans = 1
    tmp = bin_X ^ pow(2, N - n - 1)
    if tmp == 0:
        print(0)
        continue
    if i == '1':
        tmp %= cnt - 1
    else:
        tmp %= cnt + 1
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)


### FIXED CODE ###

N = int(input())
X = input()
bin_X = int(X, 2)
cnt = 0
for i in X:
    if i == '1':
        cnt += 1


def bit_count(bits):
    cnt = 0
    while bits:
        bits = bits & (bits - 1)
        bits >> 1
        cnt += 1
    return cnt


def pop_counter(n):
    return n % bit_count(n)


ans = 0
xp = bin_X % (cnt + 1)
if cnt != 1:
    xm = bin_X % (cnt - 1)
else:
    xm = 0
for n, i in enumerate(X):
    if i == '0':
        tmp = xp + pow(2, N - n - 1, cnt + 1)
        tmp %= cnt + 1
    elif cnt != 1:
        tmp = xm - pow(2,N-n-1,cnt-1)
        tmp %= cnt -1
    else:
        print(0)
        continue
    ans = 1
    while tmp != 0:
        tmp = pop_counter(tmp)
        ans += 1
    print(ans)
### BUGGY CODE ###

import sys
if sys.platform == 'ios':
	sys.stdin = open('input.txt')

input = sys.stdin.readline


n,q = map(int,input().split())
s = input()
l = [list(map(int,input().split())) for i in range(q)]

for i in range(q):
	print(s[l[i][0]-1:l[i][1]].count('AC'))

### FIXED CODE ###

import sys
if sys.platform =='ios':
	sys.stdin=open('input.txt')

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

AC=[]
for i in range(n-1):
    if s[i]=="A":
        if s[i+1]=="C":
            AC.append(i)
#print(AC)

from bisect import bisect_right as br
from bisect import bisect_left as bl
for i in range(q):
    a=bl(AC,lr[i][0]-1)
    #print(i,AC,lr[i][0],a)
    b=br(AC,lr[i][1]-2)
    #print(a,b)
    print(b-a)
### BUGGY CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
ll=sorted(A,reverse=True)
  
for n in range(N):
  if A[n]==max(A):
    print(ll[1])
  else:
    print(max(A))

### FIXED CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
ll=sorted(A)
a=max(A)
b=ll[-2]
  
for n in A:
  if n==a:
    print(b)
  else:
    print(a)
### BUGGY CODE ###

N,P = map(int,input().split())
i = round(P**(1/N))
j = 2
res = 1
if N == 1:
  print(P)
  exit()
elif P == 1|N>=40:
  print(1)
  exit()
else:
  while P%(j**N)==0:
    P = P//(j**N)
    res *= j
  j += 1
  if N >= 26:
    print(res)
    exit()
  while P%(j**N) == 0:
    P = P//(j**N)
    res *= j
  j += 2
  if N >= 18:
    print(res)
    exit()
  while P%(j**N) == 0:
    P = P//(j**N)
    res *= j
  j += 2
  if N >= 15:
    print(res)
    exit()
    
  for f in range(j,i+1,2):
    while P%(f**N) == 0:
      P = P//(f**N)
      res *= f
      
  print(res)
  exit()

### FIXED CODE ###

N,P = map(int,input().split())
i = round(P**(1/N))
res = []
if N == 1:
  print(P)
elif P == 1:
  print(1)
else:
  for i in range(i,0,-1):
    if P%i**N==0:
      print(i)
      break
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin
from heapq import heappush, heappop



readl = stdin.readline
def main():
  ## input
  N,Q = map(int, readl().rstrip().split())
  STX = [list(map(int, readl().rstrip().split())) for _ in range(N)]
  Dn = [int(readl().rstrip()) for _ in range(Q)] + [10**10]
  ans = []

  for s,t,x in sorted(STX,key=lambda x:x[2]):
    l = bisect_left(Dn,s-x)
    t -= x
    r = l
    while Dn[r] < t:
      heappush(ans, (Dn[r],x))
      r += 1
    del Dn[l:r]

  for d in Dn[:-1]:
    heappush(ans, (d,-1))

  return ans,Q


if __name__ == "__main__":
  ans,n = main()
  for _ in range(n):
    print(heappop(ans)[1])    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

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

dp = [[float("inf")] * (h + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n + 1):
    dp[i][0] = 0

for i in range(1, n + 1):
    for j in range(1, h + 1):
        a, b = ab[i-1]
        dp[i][j] = min(dp[i-1][j], dp[i][max(j-a, 0)] + b)

ans = dp[n][h]
print(ans)


### FIXED CODE ###

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

dp = [[float("inf")] * (h + 1) for _ in range(n + 1)]
for i in range(n + 1):
    dp[i][0] = 0

for i in range(1, n + 1):
    for j in range(1, h + 1):
        a, b = ab[i-1]
        dp[i][j] = min(dp[i-1][j], dp[i][max(j-a, 0)] + b)

ans = dp[n][h]
print(ans)
### BUGGY CODE ###

*c,=open(0).read().split()[2:]
print('YNEOS'[any(c.count(i)%2for i in set(c))::2])

### FIXED CODE ###

l=[0]*2**17
for i in open(0).read().split()[2:]:l[int(i)]+=1
print('YNEOS'[any(i%2for i in l)::2])
### BUGGY CODE ###

from collections import *
from bisect import *
n = int(input())
s = input()
r = deque()
g = deque()
b = deque()
ans = 0

for i in range(n):
    if s[i] == "R":
        r.append(i)
    if s[i] == "G":
        g.append(i)
    if s[i] == "B":
        b.append(i)

def cnt(x, y, z):
    global ans
    for i in x:
        index1 = bisect_left(y, i)
        if index1 <= len(y) - 1:
            for j in range(index1, len(y)):
                index2 = bisect_left(z, y[j])
                if index2 <= len(z) - 1:
                    for k in range(index2, len(z)):
                        if z[k] == y[j] + (y[j] - i):
                            ans -= 1
                    ans += len(z) - index2
cnt(r, g, b)
cnt(r, b, g)
cnt(g, r, b)
cnt(g, b, r)
cnt(b, r, g)
cnt(b, g, r)
print(ans)

### FIXED CODE ###

from itertools import permutations

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

r = [0] * n
g = [0] * n
b = [0] * n

for i in range(n):
    if s[i] == "R":
        r[i] = 1
    if s[i] == "G":
        g[i] = 1
    if s[i] == "B":
        b[i] = 1

ans = sum(r) * sum(g) * sum(b)

lst = [r, g, b]
for i in range(n - 1):
    for j in range(i + 1, n):
        k = 2 * j - i
        if k >= n:
            continue
        for x, y, z in permutations(lst):
            if x[i] and y[j] and z[k]:
                ans -= 1
print(ans)
### BUGGY CODE ###

h, n = map(int, input().split())
attack = [None] * n
cost = [None] * n
for i in range(n):
    a, c = map(int, input().split())
    attack[i] = a
    cost[i] = c
dp = [0] + [float('inf')] * h
for i in range(1, h + 1):
    for j in range(n):
        dp[i] = min(dp[i], cost[j] + dp[max(0, i - attack[j])])
print(dp[h])

### FIXED CODE ###

from sys import stdin

h, n = map(int, stdin.readline().split())
attack = [None] * n
cost = [None] * n
for i in range(n):
    a, c = map(int, stdin.readline().split())
    attack[i] = a
    cost[i] = c
dp = [0] + [float('inf')] * h
for i in range(1, h + 1):
    for j in range(n):
        dp[i] = min(dp[i], cost[j] + dp[max(0, i - attack[j])])
print(dp[h])