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

from collections import deque
from copy import deepcopy

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)]
d=[[] for _ in range(N)] # 隣接リスト
e=[-1 for _ in range(N)] #訪問ずみかどうか
g=[[ 0 for _ in range(N)] for _ in range(N)]

for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].append(b[i]-1)
    d[b[i]-1].append(a[i]-1)
f=deepcopy(d)
#print(f)

#x=0としてBFSする
v=deque([0])
e[0]=0

maxi=0
while len(v)>0:
  k=v.popleft()
  maxi=max(maxi,len(d[k]))
  all=set(i+1 for i in range(len(d[k])))
  pos=deepcopy(all)
  pos -= c[k]
  for item in d[k]:
    if e[item]==-1:
      s=min(pos)
      c[k].add(s)
      c[item].add(s)
      pos.remove(s)
      e[item] = e[k]+1
      g[k][item]=s
      g[item][k]=s
      v.append(item)
      
print(maxi)
for i in range(N-1):
  print( g[a[i]-1][b[i]-1] )

### FIXED CODE ###

from collections import deque

N=int(input())
a=[0]*(N-1)
b=[0]*(N-1)
c=[set() for _ in range(N)] # 使用している色
d=[set() for _ in range(N)] # 隣接リスト
e=[ False for _ in range(N)] #訪問ずみかどうか
f=[0]*N  #答え
for i in range(N-1):
    a[i],b[i] = map(int,input().split())
    d[a[i]-1].add(b[i]-1)
    d[b[i]-1].add(a[i]-1)

maxi=max([len(d[i]) for i in range(N-1)])
print(maxi)
#print("c:",c)
#print("d",d)
#print("e",e)

#x=0としてBFSする

v=deque([0])
e[0]=True
color=1

while v:
  p = v.popleft()
  for q in d[p]:
    if e[q]==False:
      while color in c[p]:
        color +=1
        if color>maxi:
          color=1
      c[p].add(color)
      c[q].add(color)
      f[q]=color
      e[q]=True
      v.append(q)
      
for i in range(N-1):
  print( f[b[i]-1])
### BUGGY CODE ###

n = int(input())
s = input()
count = 0


for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if s[i] != s[j] != s[k] != s[i] and j-i != k-j:
                count += 1

print(count)

### FIXED CODE ###

from collections import Counter


n = int(input())
s = input()
count = Counter(s)

ans = count["R"] * count["G"] * count["B"]
for i in range(n):
    for j in range(i+1, n):
        k = 2*j - i
        if k > n - 1:
            break
        if s[i] != s[j] != s[k] != s[i]:
            ans -= 1

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

M = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

max_vs = [''] * 10001
n, m = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
for i in range(1, n + 1):
        for v in a:
                if M[v] > i:
                        continue
                elif M[v] == i:
                        if max_vs[i] == '' or int(max_vs[i]) < v:
                                max_vs[i] = str(v)
                else:
                        if max_vs[i - M[v]] != '':
                                if max_vs[i] == '' or int(max_vs[i]) < int(str(v) + max_vs[i - M[v]]):
                                        max_vs[i] = str(v) + max_vs[i - M[v]]
print(max_vs[n])

### FIXED CODE ###

M = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

max_vs = [''] * 10001
n, m = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]
for i in range(1, n + 1):
        for v in a:
                if M[v] > i:
                        continue
                elif M[v] == i:
                        if max_vs[i] == '' or int(max_vs[i]) < v:
                                max_vs[i] = str(v)
                else:
                        if max_vs[i - M[v]] != '':
                                if (max_vs[i] == '') or (len(max_vs[i]) < len(str(v) + max_vs[i - M[v]])) or (len(max_vs[i]) == len(str(v) + max_vs[i - M[v]]) and max_vs[i] < str(v) + max_vs[i - M[v]]):
                                        max_vs[i] = str(v) + max_vs[i - M[v]]
print(max_vs[n])
### BUGGY CODE ###

MOD = 10**9 + 7
n, oddness = [int(item) for item in input().split()]
# Oddness must be even
if oddness % 2 ==  1:
    print(0)
    exit()
oddness //= 2
max_oddness = n*n + n
max_pending = n + 1

dp = [[[0] * (max_oddness) for _ in range(max_pending)] for _ in range(n)]
dp[0][0][0] = 1
dp[0][1][1] = 1
oddness_itr = [item for item in range(n*n)]
for i in range(1, n):
    for j in range(i+1):
        # Too many pending items 
        if j > n // 2:
            break
        for k in oddness_itr:
            # Connect in line
            # Oddness increase by num of pending item
            dp[i][j][k+j] += dp[i-1][j][k]
            # Choose 1 from pending items
            dp[i][j][k+j] += dp[i-1][j][k] * j*2 
            dp[i][j][k+j] %= MOD
            # Choose 2 from pending items
            if j > 0:
                dp[i][j-1][k+j-1] += dp[i-1][j][k] * j*j
                dp[i][j-1][k+j-1] %= MOD 
            # Do nothing 
            dp[i][j+1][k+j+1] += dp[i-1][j][k] 
            dp[i][j+1][k+j+1] %= MOD 

print(dp[n-1][0][oddness])

### FIXED CODE ###

MOD = 10**9 + 7
n, oddness = [int(item) for item in input().split()]
# Oddness must be even
if oddness % 2 ==  1:
    print(0)
    exit()
oddness //= 2
max_oddness = n*n + n
max_pending = n + 1

dp = [[[0] * (max_oddness) for _ in range(max_pending)] for _ in range(n)]
oddness_itr = [item for item in range(n*n)]
for i in range(n):
    if i == 0:
        dp[0][0][0] = 1
        dp[0][1][1] = 1
        continue
    for j in range(i+1):
        for k in oddness_itr:
            # Connect in line
            # Oddness increase by num of pending item
            dp[i][j][k+j] += dp[i-1][j][k]
            # Choose 1 from pending
            dp[i][j][k+j] += dp[i-1][j][k] * j*2 
            dp[i][j][k+j] %= MOD
            # Choose 2 from pending
            if j > 0:
                dp[i][j-1][k+j-1] += dp[i-1][j][k] * j*j
                dp[i][j-1][k+j-1] %= MOD 
            # Do nothing 
            dp[i][j+1][k+j+1] += dp[i-1][j][k] 
            dp[i][j+1][k+j+1] %= MOD 

print(dp[n-1][0][oddness])
### BUGGY CODE ###

s = str(input())
k = int(input())
a = []
for i in range(len(s)):
    for j in range(i,len(s)):
        a.append(s[i:j+1])
a = list(set(a))
a.sort()
print(a[k-1])

### FIXED CODE ###

s = str(input())
k = int(input())
a = []
for i in range(len(s)):
    for j in range(1,k+1):
        if i+j>len(s):
            break
        a.append(s[i:i+j])
a = list(set(a))
a.sort()
print(a[k-1])
### BUGGY CODE ###

import sys, re, os
def input(): return sys.stdin.readline().strip()
##幅優先探索
from collections import deque
 
def dfs(H,W,M):
    que = deque()
    if M[0][0] == "#":
        que.append([0,0,1,1])
    else:
        que.append([0,0,0,0])

    d = [[1,0],[0,1]]
    m = 1000000
    
    while que:
        x,y,num_sharp,in_sharp = que.popleft()

        for i,j in d:
            dx = x + i
            dy = y + j
            if 0 <= dx <= W-1 and 0 <= dy <= H-1:
                if M[dx][dy] == "#" and in_sharp:
                    que.append([dx,dy,num_sharp,1])
                elif M[dx][dy] == "#" and not in_sharp:
                    que.append([dx,dy,num_sharp+1,0])
                else:##M[dx][dy] == "."
                    que.append([dx,dy,num_sharp,0])
        if x == W-1 and y == H-1:
            m = min(m,num_sharp)
    return m 
 
 
def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(input())
    print(dfs(H,W,M))
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

def ans_dp(H,W,M):
    dp = [[0 for i in range(W)] for j in range(H)]
    flag = [[0 for i in range(W)] for j in range(H)]
    if M[0][0] == "#":
        dp[0][0] = 1
        flag[0][0] = 1
    else:
        dp[0][0] == 0
    for i in range(1,W):
        if M[0][i] == "#":
            flag[0][i] = 1
            if flag[0][i-1] == 1:
                dp[0][i] = dp[0][i-1]
            else:
                dp[0][i] = dp[0][i-1] + 1 
        else:##M[0][i] = "."
            dp[0][i] = dp[0][i-1]
    for j in range(1,H):
        if M[j][0] == "#":
            flag[j][0] = 1
            if flag[j-1][0] == 1:
                dp[j][0] = dp[j-1][0]
            else:
                dp[j][0] = dp[j-1][0] + 1 
        else:##M[0][i] = "."
            dp[j][0] = dp[j-1][0]
    
    for i in range(1,H):
        for j in range(1,W):
            if M[i][j] == "#":
                flag[i][j] = 1
                dp[i][j] = min(dp[i-1][j]+int(not flag[i-1][j]),dp[i][j-1]+int(not flag[i][j-1]))
            else:#M[i][j] == "."
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])
    """
    for i in range(H):
        print(dp[i])
    for i in range(H):
        print(flag[i])
    """
    return dp[H-1][W-1]

def main():
    H,W = map(int,input().split())
    M = []
    for i in range(H):
        M.append(list(input()))
    print(ans_dp(H,W,M))
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))

b = 2
bg = 1.0 / b

M = [] #t = i秒の最高速度
for i in range(n) :
    for j in range(T[i] * b) :
        M.append(V[i])

R = [0] + T[:]
for i in range(n) :
    R[i+1] += R[i]


for i in range(n) :

    le = R[i] * b
    ri = R[i+1] * b

    
    j = 0
    while le >= 0 :
        M[le] = min(M[le], V[i] + j*bg)
        #print(M[le])
        j += 1
        le -= 1
    j = 0
    while ri < len(M) :
        M[ri] = min(M[ri], V[i] + j*bg)
        j += 1
        ri += 1

for i in range(len(M)) :
    M[i] = min(i*bg, (len(M)-i)*bg, M[i])

M += [0]

ans = 0
for i in range(len(M)-1) :
    ans += (M[i] + M[i+1]) * bg * 0.5

print(ans)


### FIXED CODE ###

n = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))

b = 2
bg = 1.0 / b

M = [] #t = i秒の最高速度
for i in range(n) :
    for j in range(T[i] * b) :
        M.append(V[i])

R = [0] + T[:]
for i in range(n) :
    R[i+1] += R[i]


for i in range(n) :

    le = R[i] * b
    ri = R[i+1] * b

    
    j = 0
    if i-1 >= 0 and V[i-1] > V[i] :
        while le >= 0 :
            M[le] = min(M[le], V[i] + j*bg)
            #print(M[le])
            j += 1
            le -= 1
    j = 0
    if i+1 < n and V[i+1] > V[i] :
        while ri < len(M) :
            M[ri] = min(M[ri], V[i] + j*bg)
            j += 1
            ri += 1

for i in range(len(M)) :
    M[i] = min(i*bg, (len(M)-i)*bg, M[i])

M += [0]

ans = 0
for i in range(len(M)-1) :
    ans += (M[i] + M[i+1]) * bg * 0.5

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

def gcd(a,b):
    if b < a:
        b,a = a,b
    if a==0:
        return b
    
    return gcd(b%a,a)

def main():
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(1,k+1):
            tmp = gcd(i,j)
            for k in range(1,k+1):
                ans += gcd(tmp,k)
    print(ans)
    

if __name__== "__main__":
    main()

### FIXED CODE ###

def gcd(a,b):
    if b < a:
        b,a = a,b
    if a==0:
        return b
    
    return gcd(b%a,a)

def main():
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(1,k+1):
            tmp = gcd(i,j)
            for k in range(1,k+1):
                ans += gcd(tmp,k)
    print(ans)
    

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

def main(s,t):
    n = len(s)
    for i in range(n):
        if t[i]!=s[i]:
            rep =s[i]
            s=s.replace(rep,"A")
            s=s.replace(t[i],rep)
            s=s.replace("A",t[i])
    if s == t:
        print("Yes")
    else:
        print("No")
s=input()
t=input()
main(s,t)


### FIXED CODE ###

def main(s,t):
    n = len(s)
    for i in range(n):
        if t[i]!=s[i]:
            rep =s[i]
            s=s.replace(rep,"A")
            s=s.replace(t[i],rep)
            s=s.replace("A",t[i])
            if t[:i] !=s [:i]:
                return "No"
    if s == t:
        return "Yes"
    else:
        return "No"
s=input()
t=input()
print(main(s,t))
### BUGGY CODE ###

def make_divisors(n):
    divisors = []

    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    divisors.sort(reverse=True)
    return divisors


N = int(input())
A = sorted([int(x) for x in input().split()])
ans = 1

for i in range(2):
    divisors = make_divisors(A[i])

    for divisor in divisors:
        indivisible_count = 0
        for j in range(N):
            if A[j] % divisor != 0:
                indivisible_count += 1

        if indivisible_count <= 1 and divisor > ans:
            ans = divisor

print(ans)


### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    divisors.sort(reverse=True)
    return divisors


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

ans = 1
for i in range(2):
    div_list = make_divisors(A[i])

    for div_i in div_list:
        wrong_count = 0

        for A_i in A:
            if A_i % div_i != 0:
                wrong_count += 1

        if wrong_count <= 1 and div_i > ans:
            ans = div_i

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

def solve():
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort()
    CB = [list(reversed([int(i) for i in input().split()])) for _ in range(M)]
    CB = list(sorted(CB, reverse=True))

    change_list = []  # 値を変更した数の変更後の値を入れる
    no_A_flag = False
    for CiBi in CB:
        for i in range(CiBi[1]):
            if A[0] < CiBi[0]:
                change_list.append(CiBi[0])
                A.pop(0)  # 変更した値は以後変更対象となることはないのでリストから出す
                if len(A) == 0:
                    # 値をすべて変更し終わったた場合はその時点で処理終了
                    no_A_flag = True
                    break
            else:
                if i == 0:
                    # 最初の時点で変更対象外なら以降のループは行う必要がない
                    no_A_flag = True
                break
        if no_A_flag:
            break  # 変更するものがなくなれば出る
        # A.sort()

    print(sum(A) + sum(change_list))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

"""
解説を参考に作成 その3
"""


def solve():
    N, M = map(int, input().split())
    A = [int(i) for i in input().split()]
    A.sort()
    CB = [list(reversed([int(i) for i in input().split()])) for _ in range(M)]
    CB = list(sorted(CB, reverse=True))

    count = 0
    flag = False
    for cb in CB:
        for b in range(cb[1]):
            if A[count] < cb[0]:
                A[count] = cb[0]
            else:
                flag = True
                break
            count += 1
            if count >= N:
                flag = True
                break

        if flag:
            break
    print(sum(A))


if __name__ == '__main__':
    solve()
### BUGGY CODE ###

S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m] + dp[k-1][i]) % mod)
  k += 1
print(dp[k-1][5])


### FIXED CODE ###

S = input()
 
dp = [[0]*13 for j in range(len(S)+1)]
mod = 10**9+7
 
dp[0][0] = 1
k = 1
L0 = list(range(10))

for s in S:
  if ('?' == s):
    L = L0
  else:
    L = [int(s)]
 
  for l in L:
    for i in range(13):
      tmp = (i * 10) + l
      m = tmp % 13
      dp[k][m] = ((dp[k][m] + dp[k-1][i]) % mod)
  k += 1
print(dp[k-1][5])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in a:
    ans *= i
    if 1000000000000000000 < ans:
        ans = -1
        break
    elif 0 in a:
        ans = 0
        break
print (ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
if 0 in a:
    print (0)
else:
    for i in a:
        ans *= i
        if 1000000000000000000 < ans:
            ans = -1
            break
    print (ans)
### BUGGY CODE ###

from sys import stdin
def main():
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()
    ans = 0
    for i in range(len(l)-2):
        first = l[i]
        for j in range(i + 1, len(l) - 1):
            second = l[j]
            for k in range(j + 1, len(l)):
                if l[k] >= first + second:
                    break
                else:
                    ans += 1
                    #print(first, second,l[k])
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

from sys import stdin
 
def main():
    n = int(input())
    l = list(map(int, input().split()))
    l.sort()
    # print(l)
    ans = 0
    for i in range(len(l)-2):
        first = l[i]
        for j in range(i + 2, len(l)):
            second = l[j]
            s = i + 1
            e = j 
            # print("start",s, e)
            while(True):
                mid = int((s + e) / 2)
                # print("S",s, e, mid)
                
                if s == e:
                    break
                else:
                    if second >= first + l[mid]:
                        if s == mid:
                            s = e
                        else:
                            s = mid
                    else:
                        e = mid
            # print(s)
            ans += j - s
            # print("ans", ans)
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

#ABC 151 
N,M = map(int,input().split())
p = []
for i in range(M):
    p.append([str(j) for j in input().split()])
    
pena = 0
acc = 0
acc_list =[]
for m in range(M):
    for i in set([i[0] for i in p]):
        if i not in acc_list:
            if p[m][1]=='AC':
                acc_list.append(i)
                acc+=1
            else:
                pena+=1
print(str(acc) +" "+str(pena))  

### FIXED CODE ###


N,M = map(int,input().split())
PS =[""]*N
PS2 =[0]*N

PENALTY = 0
AC = 0
for m in range(M):
    p,s = map(str,input().split())
    p=int(p)-1
    if PS[p]!="AC" and s=="WA":
        PS2[p]+=1
    elif PS[p]!="AC" and s=="AC":
        AC+=1
        PENALTY+=PS2[p]
        PS[p]="AC"
        
print(AC,PENALTY)
### BUGGY CODE ###

n = int(input())
a = []
b = []
c = []
for _ in range(n):
  s, t = map(int, input().split())
  a.append(s)
  b.append(t)
  c.append(s + t)

taka = 0
aoki = 0
for i in range(n):
  p = c.index(max(c))
  x = a.pop(p)
  y = b.pop(p)
  z = c.pop(p)
  
  if i % 2 == 0:
    taka += x
  else:
    aoki += y

print(taka - aoki)

### FIXED CODE ###

n = int(input())
a = []
for _ in range(n):
  s, t = map(int, input().split())
  a.append([s+t, s, t])

a = sorted(a, key=lambda x: -x[0])
taka = 0
aoki = 0
for i in range(n):
  if i % 2 == 0:
    taka += a[i][1]
  else:
    aoki += a[i][2]

print(taka - aoki)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]

cnt = [0] * (N)
for i in range(N-1):
    if S[i:i+2] == "AC":
        cnt[i] += 1

for l, r in LR:
    print(sum(cnt[l-1:r]) - cnt[r-1])


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]

cnt, acc = [0] * N, 0
for i in range(1, N):
    if S[i-1:i+1] == "AC":
        acc += 1
    cnt[i] = acc

for l, r in LR:
    print(cnt[r-1] - cnt[l-1])
### BUGGY CODE ###

N = int(input())
S = input()

RGB = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = 2 * j - i
    if ( k >= N ):
      continue
    if (S[i] != S[j]) & (S[j] != S[k]) & (S[i] != S[k]):
      RGB -= 1


print(RGB)

### FIXED CODE ###

N = int(input())
S = input()

RGB = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = 2 * j - i
    if ( k >= N ):
      break
    if (S[i] != S[j]) & (S[j] != S[k]) & (S[i] != S[k]):
      RGB -= 1


print(RGB)
### BUGGY CODE ###

import sys
import math
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

II = input_int

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

S = input()
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = dict()

for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N-1])
    else:
        sub = int(S[N - i] + str(sub))
    rest = sub % 2019
    if rest in counter:
        counter[rest] += 1
    else:
        counter[rest] = 1

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans = 0
for r in counter.values():
    if r >= 2:
        ans += combinations_count(r, 2)
print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)
# N 文字の文字列 S から、長さ N+1 の ---累積和--- s[0], s[1], ..., s[N] を作る
# これを 2019 で割ったあまりで分類する (具体的には counter[ r ] := あまりが r のやつが何個あるか)
# 各 r ごとに、counter[r] 個から 2 個選ぶ方法の数を、足し上げる

counter = [0] * 2019
k = 10
for i in range(N + 1):
    if i == 0:
        sub = 0
    elif i == 1:
        sub = int(S[N - 1])
    else:
        sub += int(S[N - i]) * k
        k *= 10
        k %= 2019
    rest = sub % 2019
    counter[rest] += 1

ans = 0
for r in counter:
    ans += r * (r - 1) // 2
print(ans)
### BUGGY CODE ###

H, N = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

dp = [100000000] * (10 ** 5)
dp[0] = 0
for i in range(H):
    if dp[i] == 100000000:
        continue
    for j in range(N):
        a, b = AB[j]
        if dp[i] + b < dp[i + a]:
            dp[i + a] = dp[i] + b
print(min(dp[H:]))

### FIXED CODE ###

def main():
    from sys import stdin
    readline = stdin.readline
    H, N = map(int, readline().split())
    AB = [list(map(int, readline().split())) for _ in range(N)]

    dp = [100000000] * (H + 10 ** 4 + 1)
    dp[0] = 0
    for i in range(H):
        if dp[i] == 100000000:
            continue
        for j in range(N):
            a, b = AB[j]
            if dp[i] + b < dp[i + a]:
                dp[i + a] = dp[i] + b
    print(min(dp[H:]))


main()
### BUGGY CODE ###

N = int(input())
S = list(input() for i in range(N))
ans = 0
for A in range(N):
    flag = 1
    for i in range(N):
        for j in range(N):
            if S[i][(j+A)%N] != S[j][(i+A)%N]:
                flag = 0
    ans += flag*N
print(ans)

### FIXED CODE ###

N = int(input())
S = list(input() for i in range(N))
ans = 0
for A in range(N):
    flag = 1
    for i in range(N):
        for j in range(N):
            if S[i][(j+A)%N] != S[j][(i+A)%N]:
                flag = 0
    ans += flag*N
print(ans)
### BUGGY CODE ###

s=list(input())
t=list(input())
n=len(s)
m=len(t)
dp=[['' for i in range(m+1)] for j in range(n+1)]
for i in range(n):
    for j in range(m):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
        else:
            if len(dp[i+1][j])>len(dp[i][j+1]):
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
print(dp[n][m])

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    s=tuple(input())
    t=tuple(input())
    n=len(s)
    m=len(t)
    dp=[[0 for i in range(m+1)] for j in range(n+1)]
    for i in range(n):
        for j in range(m):
            if s[i]==t[j]:
                dp[i+1][j+1]=dp[i][j]+1
            else:
                if dp[i+1][j]>dp[i][j+1]:
                    dp[i+1][j+1]=dp[i+1][j]
                else:
                    dp[i+1][j+1]=dp[i][j+1]
    p=dp[n][m]
    ans=['' for _ in range(p)]
    n-=1
    m-=1
    while p>0:
        if s[n]==t[m]:
            ans[p-1]=s[n]
            n-=1
            m-=1
            p-=1
        elif dp[n+1][m+1]==dp[n][m+1]:
            n-=1
        else:
            m-=1
    print(''.join(ans)) 
if __name__=='__main__':
    main()