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

from functools import reduce
S = list(map(int,input().rstrip()))
result=0
for i in range(len(S)):
    for j in range(i+1,len(S)+1):
        n = reduce( lambda a,b:10*a+b, S[i:j])
        if n %2019==0:
            result+=1
print(result)
        

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    from functools import reduce
    import collections
     
    S = list(map(int,input().rstrip()))
    N=len(S)
    mod_list = [0]
    for i in range(1,N+1):
        new1 =pow(10,i-1,2019)
        new = (new1*S[-i]+mod_list[-1])%2019
        #print(new)
        mod_list.append(new)
        
    count = collections.Counter(mod_list)
    ans =0
    for j in range(2019):
        n = count[j]
        ans+= n*(n-1)/2
    print(int(ans))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))
l = []
for i in range(n):
  if a.count(a[i]) >= 2 and a[i] not in l:
    l.append(a[i])
if len(l) < 2:
  print(0)
  sys.exit()
l.sort()
print(l[-1]*l[-2])


### FIXED CODE ###

import heapq
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
l = []
for i in set(a):
    if c[i] >= 2:
        for j in range(c[i]//2):
            l.append(i)
if len(l) >= 2:
    print(heapq.nlargest(2, l)[0]*heapq.nlargest(2, l)[1])
else:
    print(0)
### BUGGY CODE ###

from collections import defaultdict
MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]

        if (visited[pos] > cost):
            continue
        if (pos == N - 1):
            result = max(result, cost)

        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]
            if (cost + nxt_cost > visited[nxt]):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (result, True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = defaultdict(list)
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)


### FIXED CODE ###


MAX_N = 10 ** 3 + 10
MAX_M = 2 * (10 ** 3) + 1
INF = 10 ** 13

def bfs(graph, N, M):
    que = []
    que.append([0, 0])
    visited = [-INF for x in range(MAX_N)]
    update_cnt = [0 for x in range(MAX_N)]
    result = -INF
    while (len(que) > 0):
        now = que[0]
        que.pop(0)

        pos = now[0]
        cost = now[1]
        if (visited[pos] > cost):
            continue
        for val in graph[pos]:
            nxt = val[0]
            nxt_cost = val[1]

            if (cost + nxt_cost > visited[nxt] and update_cnt[nxt] < MAX_M):
                visited[nxt] = cost + nxt_cost
                update_cnt[nxt] += 1
                que.append([nxt, nxt_cost + cost])

    if (update_cnt[N - 1] >= MAX_N):
        return (0, False)
    return (visited[N - 1], True)


if __name__ == "__main__":
    N, M = map(int, input().split())
    graph = [[] for x in range(MAX_N)]
    for x in range(M):
        a,b,c = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append([b, c])
    res,ok = bfs(graph, N, M)
    if (not ok):
        print ('inf')
    else:
        print (res)
### BUGGY CODE ###

h,w = map(int, input().split())
smap = []
for _ in range(h):
  smap.append(input().strip())

L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]
U = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]

for y in range(h):
  for x in range(w):
    if smap[y][x] == '#':
      L[y][x] = 0
      D[y][x] = 0
    else:
      if 0 < x <= w-1:
        L[y][x] = L[y][x-1] + 1
      else:
        L[y][x] = 1
      if 0 < y <= h-1:
        D[y][x] = D[y-1][x] + 1
      else:
        D[y][x] = 1

for y in range(h-1, -1, -1):
  for x in range(w-1, -1, -1):
    if smap[y][x] == '#':
      R[y][x] = 0
      U[y][x] = 0
    else:
      if 0 <= x < w-1:
        R[y][x] = R[y][x+1] + 1
      else:
        R[y][x] = 1
      if 0 <= y < h-1:
        U[y][x] = U[y+1][x] + 1
      else:
        U[y][x] = 1

ans = 0
for y in range(h):
  for x in range(w):
    tmp = L[y][x] + R[y][x] + U[y][x] + D[y][x] - 3
    if ans < tmp:
      ans = tmp

print(ans)


### FIXED CODE ###

h,w = map(int, input().split())
smap = []
for _ in range(h):
  smap.append(input().strip())

L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]
U = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]

for y in range(h):
  for x in range(w):
    if smap[y][x] == '#':
      L[y][x] = 0
      D[y][x] = 0
    else:
      if 0 < x <= w-1:
        L[y][x] = L[y][x-1] + 1
      else:
        L[y][x] = 1
      if 0 < y <= h-1:
        D[y][x] = D[y-1][x] + 1
      else:
        D[y][x] = 1

for y in range(h-1, -1, -1):
  for x in range(w-1, -1, -1):
    if smap[y][x] == '#':
      R[y][x] = 0
      U[y][x] = 0
    else:
      if 0 <= x < w-1:
        R[y][x] = R[y][x+1] + 1
      else:
        R[y][x] = 1
      if 0 <= y < h-1:
        U[y][x] = U[y+1][x] + 1
      else:
        U[y][x] = 1

ans = 0
for y in range(h):
  for x in range(w):
    tmp = L[y][x] + R[y][x] + U[y][x] + D[y][x] - 3
    if ans < tmp:
      ans = tmp

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

n = int(input())
b = list(map(int, input().strip().split()))
s = sum(b)
x = []
for i in range(n):
    y = s
    k = i + 1
    for j in range(int((n-1)/2)):
        y -= 2*b[k%n]
        k += 2
    x.append(y)
s = str(x)
s = s.replace(',','')
s = s.replace('[','')
s = s.replace(']','')
print(s)

### FIXED CODE ###

import numpy as np
n = int(input())
b = list(map(int, input().strip().split()))
s = sum(b)
x = np.zeros((n))

x[0] = s
k = 1
for i in range(int((n-1)/2)):
    x[0] -= 2*b[k%n]
    k += 2

for i in range(1,n):
    x[i] = 2 * b[i-1] - x[i-1]

x = (x.astype(int)).tolist()

s = str(x)
s = s.replace(',','')
s = s.replace('[','')
s = s.replace(']','')
s = s.replace('  ',' ')

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

n = int(input())
alist = list(map(int,input().split()))
pcount = len(set(alist))
blist = list(set(alist))
ans = 0
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

for i in range(n):
  for j in blist:
    if alist[i] == j:
      if alist.count(j)-1>=2:
        ans += cmb(alist.count(j)-1,2)

    else:
      if alist.count(j)>=2:
        ans += cmb(alist.count(j),2)
  print(ans)
  ans = 0


### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
alist = list(map(int,input().split()))
aalist = [0]*n
aset = set(alist)
adic = {}
for a in alist:
    if a not in adic:
        adic[a] = 0
    adic[a] += 1
a_counter = list(adic.items())

sigma = 0
for counter in a_counter:
    sigma += counter[1] * (counter[1] - 1) // 2

for i in range(n):
    aalist[i] = adic[alist[i]]-1

anslist = []
for a in aalist:
    anslist.append(sigma - a)

for ans in anslist:
    print(ans)
### BUGGY CODE ###

K,S = map(int, input().split())
count = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                count += 1
print(count)

### FIXED CODE ###

K,S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S-x-y
        if z >=0 and z <=K:
            count += 1
print(count)
### BUGGY CODE ###

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

import math

def permutations_count(n, r):
    if n <= 1:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

a_ = []
count_ = []
a_ = a
count = 0
ans = 0
z = 0

for k in range(n):
    ans = 0
    z += 1
    #a = a_
    count_= []
    b = a[k]
    a[k] = -1
    #print(a)
    for i in range(max(a) + 1):#探す数字
        count = 0
        for j in range(n):
            if a[j] != -1 and a[j] == i:
                    count += 1
        count_.append(count)
        #print(count_)
    for c in count_:
        ans += permutations_count(c,2)
    print(ans)
    a[k] = b
    #a = a_

### FIXED CODE ###

import collections
# import time
#start = time.time()



x=int(input())
a=list(map(int,input().split()))
 
c=collections.Counter(a)
#print(c)

num=0
for i in c.values():
    num += i*(i-1)/2
    
for i in range(x):
    print(int(num-c[a[i]]+1))
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    X, Y = [], []
    for x, y in XY:
        X.append(x)
        Y.append(y)
    X.sort()
    Y.sort()
    Xm = {x: i for i, x in enumerate(X)}
    Ym = {y: i for i, y in enumerate(Y)}
    Xr = {i: x for i, x in enumerate(X)}
    Yr = {i: y for i, y in enumerate(Y)}
    cXY = [(Xm[x], Ym[y]) for x, y in XY]
    m = 10 ** 40
    for l in range(N):
        for r in range(l + 1, N):
            for b in range(N):
                for t in range(b + 1, N):
                    k = 0
                    for x, y in cXY:
                        if l <= x <= r and b <= y <= t:
                            k += 1
                    if k >= K:
                        m = min(m, (Xr[r] - Xr[l]) * (Yr[t] - Yr[b]))
    return m
print(main())


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    X, Y = [], []
    for x, y in XY:
        X.append(x)
        Y.append(y)
    X.sort()
    Y.sort()
    Xm = {x: i for i, x in enumerate(X)}
    Ym = {y: i for i, y in enumerate(Y)}
    Xr = {i: x for i, x in enumerate(X)}
    Yr = {i: y for i, y in enumerate(Y)}
    cXY = [(Xm[x], Ym[y]) for x, y in XY]
    m = 10 ** 40
    for l in range(N):
        for r in range(l + 1, N):
            for b in range(N):
                for t in range(b + 1, N):
                    k = 0
                    for x, y in cXY:
                        if l <= x <= r and b <= y <= t:
                            k += 1
                    if k >= K:
                        m = min(m, (Xr[r] - Xr[l]) * (Yr[t] - Yr[b]))
    return m
print(main())
### BUGGY CODE ###

#

import sys
from fractions import gcd
input=sys.stdin.readline

def main():
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    l=(A[0]*A[1])//gcd(A[0],A[1])
    for i in range(2,N):
        l=(l*A[i])//gcd(l,A[i])
    ans=0
    for i in range(N):
        bi=l//A[i]
        ans+=bi
        ans%=10**9+7
    print(ans)
    
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
from fractions import gcd
input=sys.stdin.readline

def main():
    MOD=10**9+7
    N=int(input())
    A=list(map(int,input().split()))
    if N==1:
        print(1)
        exit()
    l=(A[0]*A[1])//gcd(A[0],A[1])
    for i in range(2,N):
        l=(l*A[i])//gcd(A[i],l-A[i])
    l%=MOD
    ans=0
    for i in range(N):
        ans+=l*pow(A[i],MOD-2,MOD)
        ans%=MOD
    print(ans)
    
    
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

import sys
N, M, Q = [int(i) for i in input().strip().split(' ')]

flag  = False
Ls = []
Rs = []
counter = M

d = []
for i in range(N):
    d.append([0] * N)


for line in sys.stdin:
    L, R = [int(i) for i in line.strip().split(' ')]
    if not flag:
        for i in range(L):
            for j in range(N - R + 1):
                d[i][R + j - 1] += 1
        counter -= 1
        if counter == 0:
            flag = True
    else:
        print(d[L-1][R-1])


### FIXED CODE ###

import sys
from itertools import accumulate
N, M, Q = [int(i) for i in input().strip().split(' ')]

flag  = False
counter = M

d = []
d2 = []
for i in range(N):
    d.append([0] * N)
for i in range(N):
    d2.append([0] * N)


for line in sys.stdin:
    L, R = [int(i) for i in line.strip().split(' ')]
    if not flag:
        d[L-1][R-1] += 1
#        for i in range(L):
#            for j in range(N - R + 1):
#                d[i][R + j - 1] += 1
        counter -= 1
        if counter == 0:
#            print(d)
            for i in range(N):
                d[i] = d[i][::-1]
#            print(d)
            for i in range(N):
                if i == 0:
                    d[N-1] = list(accumulate(d[N-1][::-1]))[::-1]
                else:
                    for j in range(N):
                        if j == 0:
                            temp = d[N-1-i][N-1-j]
                        else:
                            temp += d[N-1-i][N-1-j]
                        d[N-1-i][N-1-j] = d[N-i][N-1-j] + temp
#            print(d)
#            for x in d:
#                print(x)
            flag = True
    else:
        print(d[L-1][N-R])
### BUGGY CODE ###

import numpy as np
P=998244353
N,K=map(int,input().split())
LR=[]
for _ in range(K):
  l,r=map(int,input().split())
  LR+=range(l,r+1)
LR=list(set(LR))
LR=np.array(LR)
c=[0]*N
c[0]=1
for k in range(N):
  S=LR[LR<=k]
  while len(S):
    c[k]+=c[k-S[-1]]%P
    S=S[:-1]
print(c[-1]%P)

### FIXED CODE ###

P=998244353
N,K=map(int, input().split())
LR=[list(map(int, input().split())) for _ in range(K)]

s=[0 for _ in range(N+1)]
s[1]=1
for i in range(1,N):
  s[i+1] = s[i]
  for l,r in LR:
    s[i+1]+=(s[max(0,i-l+1)]-s[max(0,i-r)])%P
    s[i+1]%=P
print((s[N]-s[N-1])%P)
### BUGGY CODE ###

import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
tableud = [[0] * N for _ in range(N)]
tablelr = [[0] * N for _ in range(N)]
for i in range(N):
  x, y, _ = a[i]
  for j in range(N):
    tableud[i][j] = abs(a[j][0] - x) * a[j][2]
    tablelr[i][j] = abs(a[j][1] - y) * a[j][2]
tableudi = [[10 ** 20] * N for _ in range(1 << N)]
tablelri = [[10 ** 20] * N for _ in range(1 << N)]
for i in range(1 << N):
  for j in range(N):
    if i & (1 << j):
      for k in range(N):
        tableudi[i][k] = min(tableudi[i][k], tableud[j][k])
        tablelri[i][k] = min(tablelri[i][k], tablelr[j][k])
zero = 0
for t in range(N + 1):
  res = float("inf")
  if zero:
    print(0)
    continue
  for c in combi([x for x in range(N)], t):
    for i in range(1 << t):
      table = [10 ** 20] * N
      for j in range(N):
        table[j] = min(abs(a[j][0]), abs(a[j][1])) * a[j][2]
      x = 0
      y = 0
      for j in range(t):
        if i & (1 << j): x |= 1 << c[j]
        else: y |= 1 << c[j]
      for j in range(N):
        table[j] = min(table[j], tableudi[x][j], tablelri[y][j])
      res = min(res, sum(table))
  print(res)
  if res == 0: zero = 1


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
a = [tuple(map(int, input().split())) for _ in range(N)]
#print(a)
table = [0] * N
for k in range(N): table[k] = min(abs(a[k][0]), abs(a[k][1])) * a[k][2]
tableudi = [10 ** 12 for _ in range((1 << N) * N)]
tablelri = [10 ** 12 for _ in range((1 << N) * N)]
for i in range(1 << N):
  for j in range(N):
    if i & (1 << j):
      for k in range(N):
        ud = min(abs(a[k][0] - a[j][0]) * a[k][2], table[k])
        lr = min(abs(a[k][1] - a[j][1]) * a[k][2], table[k])
        tableudi[i * N + k] = min(tableudi[i * N + k], ud)
        tablelri[i * N + k] = min(tablelri[i * N + k], lr)
    else:
      for k in range(N):
        tableudi[i * N + k] = min(tableudi[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
        tablelri[i * N + k] = min(tablelri[i * N + k], min(abs(a[k][0]), abs(a[k][1])) * a[k][2])
res = [10 ** 12] * (N + 1)
for t in range(1 << N):
  i = t + 0
  c = bin(t).count("1")
  while True:
    x = i + 0
    y = t ^ x
    rres = 0
    for j in range(N):
      rres += min(tableudi[x * N + j], tablelri[y * N + j])
    res[c] = min(res[c], rres)
    #print(t, res, rres)
    if i == 0: break
    i = (i - 1) & t
for r in res: print(r)
### BUGGY CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    sys.setrecursionlimit(10**7)

    visit = [0 for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = [[0, dic[0]]]
    visit[0] = 1
    counter = 1
    while counter < n:
        for i in range(len(next_visit)):
            t = next_visit.pop(0)
            for s in t[1]:
                if visit[s] == 0:
                    point[s] += point[t[0]]
                    visit[s] = 1
                    counter += 1
                    next_visit.append([s, dic[s]])
    print(" ".join(map(str, point)))
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

def mp(a,b):
    if a==b:
        return 0
    else:
        ah,aw=pos[a]
        bh,bw=pos[b]
        ret=abs(ah-bh)+abs(aw-bw)
        return ret

dis=[[0]*H*W for _ in range(H*W)]
def rec(a,b):
    if a==b:
        return 0
    if dis[a-1][b-1]!=0:
        return dis[a-1][b-1]
    else:
        if dis[b-1-D][b-1]!=0:
            return rec(a,b-D)+mp(b-D,b)
        else:
            return mp(a,a+D)+rec(a+D,b)



Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    ans=rec(L,R)
    print(ans)


### FIXED CODE ###

H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    ans=S[R-1]-S[L-1]
    print(ans)
### BUGGY CODE ###

N=int(input())
A=[0 for i in range(N)]
for i in range(N):
  A[i]=int(input())

for i in range(N):
  L = A.copy()
  L[i]=0
  L.sort()
  print(L[N-1])

### FIXED CODE ###

N=int(input())
A=[0 for i in range(N)]
for i in range(N):
  A[i]=int(input())
max1=max(A)
numbers_of_max1=0
for i in range(N):
  if A[i]==max1:
    numbers_of_max1+=1
    
if numbers_of_max1>1:
  for i in range(N):
    print(max1)
else:
  L=A.copy()
  L.pop(L.index(max1))
  max2 = max(L)
  for i in range(N):
    if A[i]==max1:
      print(max2)
    else:
      print(max1)
### BUGGY CODE ###

n=int(input(''))
a= [int(s) for s in input().split(" ")]

for i in range(1,n+1):
    s=0
    for k in range(0,len(a)):
        if a[k]==i:
            s=s+1 
    print(s)

### FIXED CODE ###

n=int(input(''))
a= [int(s) for s in input().split(" ")]
t=[0]*(n+1)
for i in range(0,len(a)):
        t[a[i]]+=1
for i in range(1,n+1):
    print(t[i])
### BUGGY CODE ###

n = int(input())

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

ans = 1

for i in range(n):
  ans = ans * a[i]
      
if ans > (10 ** 18):
  print("-1") 
else:
  print(ans)

### FIXED CODE ###

n = int(input())

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

ans = 1

if 0 in a:
  ans = 0
else:
  for i in range(n):
    ans = ans * a[i]
    if ans > (10 ** 18): 
      break
      
if ans > (10 ** 18):
  print("-1") 
else:
  print(ans)
### BUGGY CODE ###

import numpy as np 
H, N = map(int, input().split())
a_list = []
b_list = []

best_at_a = None
best_at_b = None
best_at_c = 0

for _ in range(N):
    a,b =  map(int, input().split())
    a_list.append(a)
    b_list.append(b)
    
    c = a/b # コスパ
    if c>best_at_c:
        best_at_c=c
        best_at_a=a
        best_at_b=b
a_list = np.array(a_list)
b_list = np.array(b_list)


dp = [np.inf for _ in range(H)]

min_cost = np.inf
dp[0]=0
for h in range(H): # h はこれまで削った体力
    if dp[h]!=np.inf:
        for n in range(N):
            a= a_list[n]
            b= b_list[n]
            if h+a_list[n]<H:
                dp[h+a] = np.min([dp[h+a], dp[h]+b])
            elif dp[h]+b<min_cost:
                min_cost = dp[h]+b
print(int(min_cost))


### FIXED CODE ###

H, N = map(int, input().split())
inf =1000100001001000
dp = [inf for _ in range(H+1)]
 
# min_cost = np.inf
dp[0]=0
for n in range(N):
    a,b =  map(int, input().split())
    for h in range(H):
        nj = min(h+a,H)
        dp[nj] = min([dp[nj],dp[h]+b])
        
print(int(dp[H]))
### BUGGY CODE ###

import numpy as np
H,N=map(int,input().split())
AB=np.zeros([N,2]).astype(int)
for i in range(N):AB[i,:] = list(map(int,input().split()))

dp = np.zeros([H+AB[:,0].max()+1, N+1]).astype(int)
for j in range(1,H+1):
  for i in range(1,N+1):
    if AB[i-1,0] < j:
      dp[j,i] = dp[j - AB[i-1,0], i] + AB[i-1,1]
    else:
      dp[j,i] = AB[i-1,1]
  dp[j,1:] = dp[j,1:].min()

print(dp[H,1:].min())

### FIXED CODE ###

H,N=map(int,input().split())
AB = [tuple(map(int,input().split())) for _ in range(N)]
dp = [[0]*(N+1) for _ in range(2*10**4+5)]

for j in range(1,H+1):
  for i in range(1,N+1):
    if AB[i-1][0] < j:
      dp[j][i] = dp[j - AB[i-1][0]][i] + AB[i-1][1]
    else:
      dp[j][i] = AB[i-1][1]
  MIN = min(dp[j][1:])
  dp[j][1:] = [MIN]*(len(dp[j])-1)

print(min(dp[H][1:]))
### BUGGY CODE ###

INF = 10**18
A = 0
B = 0
A, B, Q = [int(s) for s in input().split()]

s = [-INF] + [int(input()) for _ in range(A)] + [INF]
t = [-INF] + [int(input()) for _ in range(B)] + [INF]


def bisect_right(a, x):
    l, r = 0, len(a)
    while r - l > 1:
        m = (l + r) // 2
        if a[m] <= x:
            l = m
        else:
            r = m
    return r


for _ in range(Q):
    q = int(input())

    sr = bisect_right(s, q)

    tr = bisect_right(t, q)

    res = INF
    for _s in s[sr-1:sr+1]:
        for _t in t[tr-1:tr+1]:
            res = min(res, abs(q-_s) + abs(_t-_s), abs(q-_t)+abs(_t-_s))

    print(res)


### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)

    res = INF
    for S in s[b-1:b+1]:
        for T in t[d-1:d+1]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)