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

h,n=map(int,input().split())
INF=10**12
a=[]
b=[]
for i in range(n):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
dp=[INF]*20010
dp[0]=0
for i in range(20010):
    for j in range(n):
        if i>=a[j]:
            dp[i]=min(dp[i],dp[i-a[j]]+b[j])
ans=min(dp[h:])
print(ans)


### FIXED CODE ###

h,n=map(int,input().split())
INF=10**12
a=[]
b=[]
for i in range(n):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
dp=[INF]*20010
dp[0]=0
for i in range(20010):
    for j in range(n):
        if i>=a[j]:
            dp[i]=min(dp[i],dp[i-a[j]]+b[j])
ans=min(dp[h:])
print(ans)
### BUGGY CODE ###

import math
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.reverse()
ans = 0
for i in range(n):
    tmp = 0
    Tmp = 0
    tmplist = [a[i]]
    index = i
    for _ in range(n-1):
        index += 1
        index %= n
        tmplist.append(a[index])
    for j in range(1,n):
        if tmplist[j] > a[i]:
            tmp += 1
    for j in range(i,n):
        if a[j] > a[i]:
            Tmp += 1
    ans += Tmp*k + tmp * (k-1)*k//2
    #print(tmplist,Tmp,tmp)
ans = ans % (10**9 + 7 )
print(ans)

### FIXED CODE ###

import math
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.reverse()
ans = 0
for i in range(n):
    tmp = 0
    Tmp = 0
    tmplist = [a[i]]
    index = i
    for _ in range(n-1):
        index += 1
        index %= n
        tmplist.append(a[index])
    for j in range(1,n):
        if tmplist[j] > a[i]:
            tmp += 1
    for j in range(i,n):
        if a[j] > a[i]:
            Tmp += 1
    ans += Tmp*k + tmp * (k-1)*k//2
    #print(tmplist,Tmp,tmp)
ans = ans % (10**9 + 7 )
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
A,B,K=map(int,input().split())

for i in range(K):
    if A>=1:
        A-=1
    elif B>=1:
        B-=1
print(A,end=' ')
print(B)

### FIXED CODE ###

# coding: utf-8
# Your code here!
A,B,K=map(int,input().split())

if A<=K:
    K-=A
    A=0
    if B<=K:
        print(0, end=' ')
        print(0)
    else:
        B-=K
        print(A,end=' ')
        print(B)

else:
    A-=K
    print(A,end=' ')
    print(B)
### BUGGY CODE ###

n=int(input())
k=int(input())
s=len(list(str(n)))
if k==1:
    ans=(s-1)*9
    for i in range(9):
        if n>=(10**(s-1))*(i+1):
            ans+=1
elif k==2:
    ans=9*9*(s-1)*(s-2)//2
    for i in range(9):
        for j in range(s-1):
            for p in range(9):
                if n>=(10**(s-1))*(i+1)+(10**j)*(p+1):
                    ans+=1
else:
    ans=9*81*(s-1)*(s-2)*(s-3)//6
    for i in range(9):
        for p in range(s-1):
            for q in range(s-1):
                if p<q:
                    for t in range(1,10):
                        for u in range(1,10):
                            if n>=(10**(s-1))*(i+1)+(10**p)*t+(10**q)*u:
                                ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
k=int(input())
s=len(list(str(n)))
if k==1:
    ans=(s-1)*9
    for i in range(9):
        if n>=(10**(s-1))*(i+1):
            ans+=1
elif k==2:
    ans=9*9*(s-1)*(s-2)//2
    for i in range(9):
        for j in range(s-1):
            for p in range(9):
                if n>=(10**(s-1))*(i+1)+(10**j)*(p+1):
                    ans+=1
else:
    ans=9*81*(s-1)*(s-2)*(s-3)//6
    f=int(list(str(n))[0])
    ans+=(f-1)*81*(s-1)*(s-2)//2
    for p in range(s-1):
        for q in range(s-1):
            if p<q:
                for t in range(1,10):
                    for u in range(1,10):
                        if n>=(10**(s-1))*f+(10**p)*t+(10**q)*u:
                            ans+=1
print(ans)
### BUGGY CODE ###

l, r = map(int, input().split())

LUT = [[(i*j)%2019 for i in range(2019)] for j in range(2019)]

ans = 2019 ** 2

for i in range(l, r + 1):
  for j in range(i + 1, r + 1):
    ans = min(ans, LUT[i % 2019][j % 2019] % 2019)
    if ans == 0:
      break
    
print(ans)

### FIXED CODE ###

def main():
  l, r = map(int, input().split())
  LUT = [[(i*j)%2019 for i in range(2019)] for j in range(2019)]
  ans = 2018
  m = 2019
  for i in range(l, r + 1):
    for j in range(i + 1, r + 1):
      ans = min(ans, LUT[i % m][j % m])
      if ans == 0:
        return 0
  return ans

print(main())
### BUGGY CODE ###

N = int(input())
S = [x[:1] for x in input()]
ans = 0
count = 0

#1番西
SC1,SE1 = S[0],S[1:]
count = SE1.count("E")

ans = count
#print(ans)

#2番目からN-1番目まで
for i in range(1,len(S) - 1):
    SW,SC,SE  = S[0:i], S[i], S[i:len(S)]
    count = SW.count("W") + SE.count("E")
    if count <= ans:
        ans = count

    #print(SW,SC,SE,count,ans)


#N番目
SWN,SCN,count = S[:len(S) - 2], S[len(S) - 1], 0
count = SWN.count("W")
if count <= ans:
    ans = count

print(ans)

### FIXED CODE ###

N = int(input())
S = [x[:1] for x in input()]
ans = 0
count = 0

ruiE, ruiW = [], []
ruie,ruiw = 0, 0
for i in range(len(S)):
    if S[i] == "E":
        ruie += 1
    elif S[i] == "W":
        ruiw += 1

    ruiE.append(ruie)
    ruiW.append(ruiw)

#print(ruiE,ruiW)

def countW(j):
    return ruiW[j]

def countE(i):
    return ruiE[len(S) - 1] - ruiE[i-1]

#for i in range(1,5):
#    print(countW(i),countE(i))

#西端
ans = 0 + countE(1)

#間
for h in range(1, len(S)-1):
    count = countW(h-1) + countE(h+1)

    if count <= ans:
        ans = count

   # print(count,ans)

#東端
count = countW(len(S)-2) + 0

if count <= ans:
    ans = count

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

H, W = map(int, input().split())

data = [[-W]*W for i in range(H)]

for i in range(H):
    s = input()
    x = -(2*W)
    for j in range(W):
        if s[j] == '#':
            x = 0
        data[i][j] = x
        x += 1
    x = -(2*W)
    for j in range(W):
        if data[i][W-j-1] == 0:
            x = 0
        elif data[i][W-j-1] < 0:
            data[i][W-j-1] = x
        else:
            if x > 0:
                x = min(x, data[i][W-j-1])
            else:
                x = data[i][W-j-1]
            data[i][W-j-1] = x
        x += 1


for w in range(W):
    x = -(2*H)
    for h in range(H):
        if data[h][w] == 0:
            x = 0
        elif data[h][w] > 0:
            if x > 0:
                x = min(x, data[h][w])
            else:
                x = data[h][w]
            data[h][w] = x
        else:
            data[h][w] = x
        x += 1
    x = -(2*H)
    for h in range(H):
        if data[H-h-1][w] == 0:
            x = 0
        elif data[H-h-1][w] > 0:
            if x > 0:
                x = min(x, data[H-h-1][w])
            else:
                x = data[H-h-1][w]
            data[H-h-1][w] = x
        else:
            data[H-h-1][w] = x
        x += 1

ans = 0
for d in data:
    ans = max(ans, max(d))
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())

data = [[-W]*W for i in range(H)]

for i in range(H):
    s = input()
    x = -(2*W)
    for j in range(W):
        if s[j] == '#':
            x = 0
        data[i][j] = x
        x += 1
    x = -(2*W)
    for j in range(W):
        if data[i][W-j-1] == 0:
            x = 0
        elif data[i][W-j-1] < 0:
            data[i][W-j-1] = x
        else:
            if x > 0:
                x = min(x, data[i][W-j-1])
            else:
                x = data[i][W-j-1]
            data[i][W-j-1] = x
        x += 1


for w in range(W):
    x = -(2*H)
    for h in range(H):
        if data[h][w] == 0:
            x = 0
        elif data[h][w] > 0:
            if x > 0:
                x = min(x, data[h][w])
            else:
                x = data[h][w]
            data[h][w] = x
        else:
            data[h][w] = x
        x += 1
    x = -(2*H)
    for h in range(H):
        if data[H-h-1][w] == 0:
            x = 0
        elif data[H-h-1][w] > 0:
            if x > 0:
                x = min(x, data[H-h-1][w])
            else:
                x = data[H-h-1][w]
            data[H-h-1][w] = x
        else:
            data[H-h-1][w] = x
        x += 1

ans = 0
for d in data:
    ans = max(ans, max(d))
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
S = input()
n=0
flg=0
#print(s[0:K-1]+s[K-1].lower()+s[K:N])
while(not S==""):

#    if  S[n:].startswith("dreameraser"):
#        n=n+11
        #print(S[n:])
        #flg==1
#        continue
    if S.endswith("dreamer"):
        #n=n+6
        S=S[::-1]
        S=S.replace("dreamer","",1)
        S=S[::-1]
        #print(S[n:])
        continue
    elif S.endswith("dream"):
        #n=n+5
        S=S[::-1]
        S=S.replace("dream","",1)
        S=S[::-1]
        #print(S)
        #flg==1
        continue
    elif S.endswith("eraser"):
        #n=n+6
        S=S[::-1]
        S=S.replace("eraser","",1)
        S=S[::-1]
        #print(S[n:])
        continue
    elif S.endswith("erase"):
        #n=n+5
        S=S[::-1]
        S=S.replace("erase","",1)
        S=S[::-1]
        #print(S)
        #flg==1
        continue
    print("NO")
    exit()

print("YES")


### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
#N, K = map(int, input().split())
# 文字列の入力
S = input()
n=0
flg=0
#print(s[0:K-1]+s[K-1].lower()+s[K:N])
S=S[::-1]
while(not S==""):

#    if  S[n:].startswith("dreameraser"):
#        n=n+11
        #print(S[n:])
        #flg==1
#        continue
    if S.startswith("remaerd"):
        #n=n+6
        S=S.replace("remaerd","",1)
        #print(S[n:])
        continue
    elif S.startswith("maerd"):
        #n=n+5
        S=S.replace("maerd","",1)
        #print(S)
        #flg==1
        continue
    elif S.startswith("resare"):
        #n=n+6
        S=S.replace("resare","",1)
        #print(S[n:])
        continue
    elif S.startswith("esare"):
        #n=n+5
        S=S.replace("esare","",1)
        #print(S)
        #flg==1
        continue
    print("NO")
    exit()

print("YES")
### BUGGY CODE ###

S = list(str(input()))
T = list(str(input()))
check = 1
SC = [e for e in set(S) if S.count(e) > 1]
TC = [e for e in set(T) if T.count(e) > 1]
while len(S) > 0:
  if S[0] not in SC and T[0] not in TC:
    S.pop(0)
    T.pop(0)
  elif S[0]in SC and T[0] in TC:
    idxS = [j for j, x in enumerate(S) if x == S[0]]
    idxT = [j for j, x in enumerate(T) if x == T[0]]
    if idxS == idxT:
      for i in idxS[::-1]:
        S.pop(i)
        T.pop(i)
    else:
      check = 0
      break
  else:
    check = 0
    break
if check:
  print("Yes")
else:
  print("No")
  

### FIXED CODE ###

S = list(str(input()))
T = list(str(input()))
check = 1
bij1 = {}
bij2 = {}
for i in range(len(S)):
  if S[i] in bij1 and bij1[S[i]] != T[i]:
    check = 0
    break
  elif T[i] in bij2 and bij2[T[i]] != S[i]:
    check = 0
    break
  elif S[i] not in bij1 and T[i] not in bij2:
    bij1[S[i]] = T[i]
    bij2[T[i]] = S[i]
    
if check:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    dp=[[None]*(n+1) for _ in range(n+1)]

    def dfs(l,r):
        if(dp[l][r] is not None): return
        if(l==r):
            dp[l][r]=0
            return

        # 1個先の値を確定させておく
        dfs(l+1,r)
        dfs(l,r-1)
        turn=(n-(r-l))%2
        if(turn==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])

    dfs(0,n)
    print(dp[0][n])
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    dp = [[None] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][i] = 0

    for width in range(1, n + 1):
        for l in range(n):
            r = l + width
            if r > n:
                break
            turn = (n - (r - l)) & 1
            if turn & 1 == 0:
                dp[l][r] = max(A[l] + dp[l + 1][r], A[r - 1] + dp[l][r - 1])
            else:
                dp[l][r] = min(-A[l] + dp[l + 1][r], -A[r - 1] + dp[l][r - 1])


    print(dp[0][n])
resolve()
### BUGGY CODE ###

N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        r[i][j] = r[i][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
    print(q)


### FIXED CODE ###

N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if i == 0:
            r[i][j] = p[i][j] + r[i][j-1]      
        elif j == 0:
            r[i][j] = p[i][j] +r[i-1][j]
        else:
            r[i][j] = r[i-1][j] + r[i][j-1] - r[i-1][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    if Qlist[i][0] == 1:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1]
    else:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1] - r[Qlist[i][0]-2][Qlist[i][1]-1]
    print(b)
### BUGGY CODE ###

import sys
#import numpy as np
import bisect
sys.setrecursionlimit(10 ** 7)

# TLE
# PyPy3 (2.4.0) 2112 ms

N, Q = map(int, input().split())
STX = []
for _ in range(N):
    s, t, x = map(int, input().split())
    STX.append((s, t, x))

PEOPLE = []
for i in range(Q):
    d = int(input())
    PEOPLE.append((d, i))

ans = [-1] * Q

STX.sort(key=lambda x: x[2])

for s, t, x in STX:
    if len(PEOPLE) == 0:
        break

    i = bisect.bisect_left(PEOPLE, (s - x, -1))
    j = bisect.bisect_left(PEOPLE, (t - x, -1))

    if i == j:
        continue

    use = [PEOPLE[x][1] for x in range(i, j)]

    #print(len(PEOPLE), use)

    for k in use:
        if ans[k] == -1:
            ans[k] = x

    PEOPLE = [PEOPLE[x] for x in range(len(PEOPLE)) if not(i <= x < j)]


print("\n".join(map(str, ans)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

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

from sys import stdin

n = int(stdin.readline().rstrip())
s = []
d = [0] * 200000 
max = 1

for i in range(n):
    t = stdin.readline().rstrip()
    d[i] = 1
    for ss in s:
        if t == ss:
            d[i] = d[i] + 1
            if max < d[i]:
                max = d[i]
    s.append(t)

result = []        
for cnt in range(len(d)):
    if d[cnt] == max:
        result.append(s[cnt])

result.sort()
for r in result:
    print(r)


### FIXED CODE ###

from sys import stdin
import math

n = int(stdin.readline().rstrip())

d = {}
max = 0
for i in range(n):
    s = stdin.readline().rstrip()
    if s in d.keys():
        d[s] += 1
    else:
        d[s] = 1
    if max < d[s]:
        max = d[s]

result = []
for key, value in d.items():
    if value == max:
        result.append(key)

result.sort()

for i in range(len(result)):
    print(result[i])
### BUGGY CODE ###

N = int(input())
S = []
for i in range(N):
    s = input()
    S.append("".join(sorted(s)))

S.sort()

k = 0
for i in range(N):
    for j in range(i+1,N):
        if S[i] == S[j]:
            k += 1
        else:
            break
print(k)


### FIXED CODE ###

N = int(input())
k = 0
h = {}
for i in range(N):
    s = input()
    ss = "".join(sorted(s))
    if ss in h:
        k += h[ss]
    else:
        h[ss] = 0
    h[ss] += 1

print(k)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**9)


def main():
    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        edges[a].append(b)
        edges[b].append(a)

    cnt = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    visited = [False]*N
    visited[0] = True

    def dfs(v: int):
        nonlocal visited
        nonlocal cnt
        if all(visited):
            print(*cnt)
            sys.exit()
        for n in edges[v]:
            if visited[n]:
                continue
            visited[n] = True
            cnt[n] += cnt[v]
            dfs(n)
        return

    dfs(0)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10**9)


def main():
    N, Q = map(int, input().split())
    edges = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(lambda x: int(x)-1, input().split())
        edges[a].append(b)
        edges[b].append(a)

    cnt = [0]*N
    for _ in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x

    visited = [False]*N
    visited[0] = True
    q = deque([0])
    while q:
        v = q.pop()
        for n in edges[v]:
            if visited[n]:
                continue
            visited[n] = True
            cnt[n] += cnt[v]
            q.append(n)
    print(*cnt)


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

s = input()
q = int(input())
arr = [list(input().split()) for i in range(q)]

for i in arr:
    if len(i) == 1:
        s = s[::-1]
    else:
        if i[1] == '1':
            s = i[2] + s
        else:
            s = s + i[2]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
arr = [list(input().split()) for i in range(q)]
mae1 = 0
mae = []
ato = []
for i in arr:
    if i[0] == '1':
        mae1 = 0 if mae1 == 1 else 1
    else:
        if mae1 == 0:
            if i[1] == '1':
                mae.append(i[2])
            else:
                ato.append(i[2])
        else:
            if i[1] == '1':
                ato.append(i[2])
            else:
                mae.append(i[2])
mae = ''.join(mae)
ato = ''.join(ato)
ans = mae[::-1] + s + ato
if mae1 == 1:
    ans = ans[::-1]
print(ans)
### BUGGY CODE ###

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

while M:
  m = A.index(max(A))
  A[m] //= 2
  M -= 1
print (sum(A))


### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)

while M:
  m = heapq.heappop(A) * (-1)
  heapq.heappush(A, (-1) * (m // 2))
  M -= 1
print (sum(A) * (-1))
### BUGGY CODE ###

def main():
    import fractions
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = tuple(map(int,input().split()))
    g = a[0]
    MOD = 10**9+7
    for i in range(1,N):
        t = a[i]
        #g = g*a[i]//fractions.gcd(g,a[i])
        g = divmod(g*t,fractions.gcd(g,t))[0]
    res = 0
    for i in range(N):
        res += (g//a[i])%MOD
    print(res%MOD)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)
### BUGGY CODE ###

from collections import Counter
N = int(input())
p = list(map(int, input().split()))

cnt = Counter(p)

ps = set(p)
plst = list(ps)
plst.sort(reverse=True)
temp = plst[:]
ans = 0
while temp:
    q = temp.pop()
    lst = []
    for i in temp:
        if i%q!=0: lst.append(i)
    if cnt[q] == 1: ans += 1
    temp = lst[:]

print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
p = list(map(int, input().split()))

cnt = Counter(p)

ps = set(p)
plst = list(ps)
plst.sort()

ans = [0] * (plst[-1] + 1)

for i in range(len(plst)):
    for j in range(plst[i], plst[-1]+1, plst[i]):
        ans[j] += 1
d = 0
for i in range(len(plst)):
    if ans[plst[i]]==1 and cnt[plst[i]]==1: d += 1
print(d)
### BUGGY CODE ###

from collections import Counter

s = input()
l = len(s)
s = int(s)

rests = []

d = 10**(l-1)

while s > 0:
    r = s % 2019
    rests.append(r)

    s = s % d
    d = d // 10

a = 0

c = Counter(rests)

for v in c.values():
    if v >= 2:
        a += v * (v-1) // 2

a += c[0]

print(a)





### FIXED CODE ###

from collections import defaultdict

s = input()

rests = [0]
n = 0
a = 0
m = 1
c = defaultdict(int)
c[0] += 1
for i in list(s)[::-1]:
    n = n + int(i)*m

    c[n % 2019] += 1
    m = m * 10 % 2019

for v in c.values():
    a += v * (v-1) // 2
print(a)
### BUGGY CODE ###

N, Q = map(int, input().split())
C = list(map(int, input().split()))
Query = [tuple(map(int, input().split())) for _ in range(Q)]
Ans = []
D = dict()

Ans.append(D.copy())
for c in C:
    if c in D:
        D[c] += 1
    else:
        D[c] = 1
    Ans.append(D.copy())

for l, r in Query:
    l -= 1
    ans = Ans[r].items() - Ans[l].items()
    print(len(ans))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
Color = [0] + list(map(int, input().split()))
Query =[]
for i in range(Q):
    l, r = map(int, input().split())
    Query.append(r * 10 ** 12 + l * 10 ** 6 + i)
Query.sort()
Ans = [0] * Q

BIT = [0] * (N + 1)  # BITを使う


def BIT_query(idx):  # idxまでの合計を返す
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum


def BIT_update(idx,x):  # idxにxを足す
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return


cn = max(Color)
Last = [-1] * cn

cnt = 0
for q in Query:
    r = q // 10 ** 12
    l = (q % 10 ** 12) // 10 ** 6
    i = q % 10 ** 6
    while cnt < r:
        cnt += 1
        c = Color[cnt] - 1
        if Last[c] == -1:
            Last[c] = cnt
            BIT_update(cnt, 1)
        else:
            x = Last[c]
            BIT_update(x, -1)
            Last[c] = cnt
            BIT_update(cnt, 1)
    Ans[i] = BIT_query(r) - BIT_query(l-1)

for a in Ans:
    print(a)
### BUGGY CODE ###

n,m=list(map(int, input().split()))
h=list(map(int, input().split()))
p=[]
remain = set(range(1, n+1))
for i in range(m):
    p.append(list(map(int, input().split())))
p.sort()
temp = []
for a,b in p:
    temp.append([b,a])
p = p + temp
p.sort()
for a,b in p:
    if not (a in remain):
        continue
    if h[a-1]<=h[b-1]:
        remain = remain - set([a])
print(len(remain))

### FIXED CODE ###

n,m=list(map(int, input().split()))
h=list(map(int, input().split()))
p=[]
remain = set(range(1, n+1))
for i in range(m):
    p.append(list(map(int, input().split())))
temp = []
for a,b in p:
    temp.append([b,a])
p = p + temp
delset = set()
for a,b in p:
    if h[a-1]<=h[b-1]:
        #remain = remain - set([a])
        delset.add(a)
remain = remain - delset
print(len(remain))
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
a1 = []
for i in range(a,b+1):
    for j in range(c,d+1):
        a1.append(i*j)
print(max(a1))

### FIXED CODE ###

a,b,c,d = map(int,input().split())
a1 = []
e = [a,b]
f = [c,d]
for i in e:
    for j in f:
        a1.append(i*j)
print(max(a1))