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

from itertools import *
from collections import *
h,w=map(int,input().split())
a=[]
l=[(0,1),(0,-1),(1,0),(-1,0)]
for i in range(h):
    t=list(input())
    a.append(t)
ans=[[float("inf")]*w for i in range(h)]
q=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            ans[i][j]=0
            q.append((i,j))
while q:
    x,y=q.popleft()
    for xx,yy in l:
        nx,ny=x+xx,y+yy
        if 0<=nx<h and 0<=ny<w:
            if ans[nx][ny]>ans[x][y]+1:
                ans[nx][ny]=ans[x][y]+1
                if (nx,ny) not in q:
                    q.append((nx,ny))
aa=[]
for i in range(h):
    aa.append(max(ans[i]))
print(max(aa))


### FIXED CODE ###

from collections import deque
H,W=map(int, input().split())
 
A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0
 
d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)
print(ans)
### BUGGY CODE ###


N = int(input())
if N >= 1000000:
    ans = 13969985
    N -= 1000000
else:
    ans = 0 

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

for i in range(N):
    AB = make_divisors(i)
    ans += len(AB)

print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for a in range(1, n):
    ans += (n - 1) // a
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]
    L = [[0] * w for _ in range(h)]
    R = [[0] * w for _ in range(h)]
    U = [[0] * w for _ in range(h)]
    D = [[0] * w for _ in range(h)]
    ans = 0
    for i in range(h):
        for j in range(w):
            if j != 0:
                L[i][j] = L[i][j - 1]
            if s[i][j] == ".":
                L[i][j] += 1
            else:
                L[i][j] = 0
    for i in range(h):
        for j in range(w - 1, -1, -1):
            if j != w - 1:
                R[i][j] = R[i][j + 1]
            if s[i][j] == ".":
                R[i][j] += 1
            else:
                R[i][j] = 0
    for j in range(w):
        for i in range(h):
            if i != 0:
                U[i][j] = U[i - 1][j]
            if s[i][j] == ".":
                U[i][j] += 1
            else:
                U[i][j] = 0
    for j in range(w):
        for i in range(h - 1, -1, -1):
            if i != h - 1:
                D[i][j] = D[i + 1][j]
            if s[i][j] == ".":
                D[i][j] += 1
            else:
                D[i][j] = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() for _ in range(h)]
L = [[0] * w for _ in range(h)]
R = [[0] * w for _ in range(h)]
U = [[0] * w for _ in range(h)]
D = [[0] * w for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if j != 0:
            L[i][j] = L[i][j - 1]
        if s[i][j] == ".":
            L[i][j] += 1
        else:
            L[i][j] = 0
for i in range(h):
    for j in range(w - 1, -1, -1):
        if j != w - 1:
            R[i][j] = R[i][j + 1]
        if s[i][j] == ".":
            R[i][j] += 1
        else:
            R[i][j] = 0
for j in range(w):
    for i in range(h):
        if i != 0:
            U[i][j] = U[i - 1][j]
        if s[i][j] == ".":
            U[i][j] += 1
        else:
            U[i][j] = 0
for j in range(w):
    for i in range(h - 1, -1, -1):
        if i != h - 1:
            D[i][j] = D[i + 1][j]
        if s[i][j] == ".":
            D[i][j] += 1
        else:
            D[i][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

n,q=map(int,input().split())
G=[[] for i in range(n)] #隣接配列
P=[0]*n #根のポイント
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    p-=1
    P[p]+=x
    

def dfs(s,p=-1,cnt=0):
    cnt+=P[s]
    P[s]=cnt
    for i in G[s]:
        if i!=p:
            dfs(i,s,cnt)

dfs(0)
print(*P,sep=" ")

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque

def main():
    n,q=map(int,input().split())
    G=[[] for i in range(n)] #隣接配列
    P=[0]*n #親のポイント
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1
        b-=1
        G[a].append(b)
        G[b].append(a)
    for i in range(q):
        p,x=map(int,input().split())
        p-=1
        P[p]+=x
    
    Chk=[0]*n #訪問済みチェック
    q=deque([0])
    while q: #qが空になるまで(BFS:幅優先探索)
        now=q.popleft() #取り出す
        Chk[now]=1 #訪問済みにする
        for i in G[now]: #子に対し
            if Chk[i]==0: #未訪問のとき
                P[i]+=P[now] #ポイント加算
                q.append(i) #親としてqに入れる

    print(*P)

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

def ABC051B(k, s):
    count = 0
    for x in range(k+1):
        for y in range(k+1):
            for z in range(k+1):
                if x + y + z == s:
                    count += 1

    print(count)

k, s = map(int, input().split())
ABC051B(k, s)


### FIXED CODE ###

def ABC051B(k, s):
    a = [0] * (3 * k + 1)
    mx = -(-3 * (k + 1) ** 2 // 4)
    for i in range(k + 1):
        a[i] = (i + 1) * (i + 2) // 2
        a[3 * k - i] = (i + 1) * (i + 2) // 2
    if k % 2 == 0:
        max_point = 3 * (k // 2)
        a[max_point] = mx
        odd_cum_diff = [x ** 2 for x in range(k // 2)]
        for j in range(k // 2):
            a[max_point - j] = mx - odd_cum_diff[j]
            a[max_point + j] = mx - odd_cum_diff[j]
    else:
        max_point = 3 * (k // 2) + 1
        a[max_point] = mx
        even_cum_diff = [x * (x + 1) for x in range(k // 2)]
        for j in range(k // 2):
            a[max_point - j] = mx - even_cum_diff[j]
            a[max_point + j + 1] = mx - even_cum_diff[j]
    # for i, v in enumerate(a):
    #     print(i, v)
    print(a[s])

k, s = map(int, input().split())
ABC051B(k, s)
### BUGGY CODE ###

n = int(input())
l = [input() for i in range(n)]
new_l = []

for i in l:
  if not i in new_l:
    new_l.append(i)
    
a = len(new_l)
print(a)

### FIXED CODE ###

n = int(input())
l = [input() for i in range(n)]
 
l = set(l)
l = list(l)
print(len(l))
### BUGGY CODE ###

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n,wmax=IL()
dp=[[0 for i in range(wmax+1)] for j in range(n+1)]
for i in range(1,n+1):
    w,v=IL()
    for j in range(wmax+1):
        if j<w:
            dp[i][j]=dp[i-1][j]
        else:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-w]+v)
print(dp[n][wmax])

### FIXED CODE ###

import numpy as np
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return input()

n,wmax=IL()
dp=np.zeros(wmax+1,dtype=int)
for i in range(n):
    w,v=IL()
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[wmax])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7
A.sort()
ans = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i] > A[j]:
            continue
        ans += A[i] * A[j] % MOD

print(ans % MOD)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7
A.sort()
ans = 0
sumA = sum(A)
for i in range(N):
    sumA -= A[i]
    for j in range(i+1,N):
        if A[i] > A[j]:
            continue
        ans += (A[i] * (sumA % MOD)) %MOD
        break

print(ans % MOD)
### BUGGY CODE ###

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

for i in range(1,10**9):
  if (abs(A-i) == abs(B-i)):
      print(i)
      exit()

print("IMPOSSIBLE")

### FIXED CODE ###

A, B = map(int,input().split())
 
if (A % 2 != B % 2):
  print("IMPOSSIBLE")
else:
  print(int((A + B) / 2))
### BUGGY CODE ###

from collections import deque
import itertools
import copy
import numpy as np

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

def solve(S, s, g):
    M = copy.deepcopy(S)
    d = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    queue = deque([s])
    steps = [[np.max for _ in range(W)] for _ in range(H)]
    steps[s[0]][s[1]] = 0

    while len(queue) > 0:
        current = queue.popleft()
        cy = current[0]
        cx = current[1]
        if cy == g[0] and cx == g[1]:
            return steps[cy][cx]
        else:
            M[cy][cx] = '#'
            for i in d:
                next = [cy+i[0], cx+i[1]]
                # はみ出さないかつ通ってない
                if (0<=next[0]<H and 0<=next[1]<W) and M[next[0]][next[1]]!='#':
                    queue.append(next)
                    steps[next[0]][next[1]] = steps[cy][cx] + 1
        
# print(solve(S, [0, 0], [0, 1]))
# print(solve(S, [2, 0], [0, 4]))

# print(S)
maxStep = 0
for s in itertools.product(range(H), range(W)):
    for g in itertools.product(range(H), range(W)):
        if S[s[0]][s[1]] == '.' and S[g[0]][g[1]] == '.':
            # print(s, g)
            # print(solve(S, [s[0], s[1]], [g[0], g[1]]))
            maxStep = max(solve(S, [s[0], s[1]], [g[0], g[1]]), maxStep)

print(maxStep)

### FIXED CODE ###

from collections import deque
import itertools
import copy

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

def solve(s):
    M = copy.deepcopy(S)
    d = ((1, 0), (-1, 0), (0, -1), (0, 1))
    queue = deque([s])
    steps = [[-1 for _ in range(W)] for _ in range(H)]
    steps[s[0]][s[1]] = 0

    while len(queue) > 0:
        current = queue.popleft()
        cy = current[0]
        cx = current[1]
        # M[cy][cx] = '#'
        for i in d:
            ny = cy+i[0]
            nx = cx+i[1]
            # はみ出さないかつ通ってない
            if (0<=ny<H and 0<=nx<W) and M[ny][nx]=='.' and steps[ny][nx] < 0:
            # if (0<=ny<H and 0<=nx<W) and M[ny][nx]!='#':
                queue.append([ny, nx])
                steps[ny][nx] = steps[cy][cx] + 1
        
    return max([max(i) for i in steps])

maxStep = 0
for s in itertools.product(range(H), range(W)):
    if S[s[0]][s[1]] == '.':
        maxStep = max(solve([s[0], s[1]]), maxStep)

print(maxStep)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))

m = p[0:K]
for i in range(1,N-K+1):
    if sum(m) < sum(p[i:K+i]):
        m = p[i:K+i]

t = [0] * K
for l in range(0,K):
     t[l] = (1+m[l])/2
n = sum(t)
print(n)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))

s = 0
for i in range(0,K):
    s = s + p[i]
t = s
for j in range(0,N-K):
    u = s + p[j+K] - p[j]
    if u > t:
        t = u
    s = u
print((t+K)/2)
### BUGGY CODE ###

def main():
    import sys
    from collections import Counter

    input = sys.stdin.readline

    s = str(input().rstrip())
    num = ""
    li = []
    f = 0
    mi = 0
    li_append = li.append

    for i in range(1, len(s) + 1):
        num = s[-i] + num
        li_append(int(num) % 2019)
        if num[0] == "0":
            f += 1
        else:
            if f > 0:
                mi += ((f + 1) * f) // 2
                f = 0
            else:
                continue

    co = Counter(li)
    val = [i for i in co.values() if i > 1]
    ans_1 = 0

    ans_1 = sum(map(lambda x: (x*(x-1))//2, val))
    ans2 = 0
    if 0 in co:
        ans2 = co[0]
    print(ans_1 + ans2 - mi)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    dic = defaultdict(int)

    input = sys.stdin.readline

    s = str(input().rstrip())
    m = 0
    before_m = 0.1

    for i in range(1, len(s) + 1):
        before_m = int(before_m*10)%2019
        m_ad = (int(s[-i]) * before_m) % 2019
        m = (m_ad + m) % 2019
        dic[m] += 1

    ans1 = 0

    for x in dic.values():
        if x > 1:
            ans1 += x * (x - 1) // 2
    ans2 = dic[0]

    print(ans1 + ans2)

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

N = int(input())
S = input()
nums = []
for i in range(N):
    nums.append(S[0: i].count("W") + S[i + 1:].count("E"))
print(min(nums))

### FIXED CODE ###

N = int(input())
S = input()
for i in range(N):
    if i == 0:
        num = S[i + 1:].count("E")
        num_min = num
    else:
        if S[i - 1] == "W":
            num += 1
        if S[i] == "E":
            num -= 1
        if num < num_min:
            num_min = num
print(num_min)
### BUGGY CODE ###

import numpy as np
MOD = 10 ** 9 + 7
S = input()
N = len(S)
mod13 = [np.zeros((13,), dtype=np.int64) for _ in range(N + 1)]
mod13[0][0] = 1
exponent = 1
for i in range(1, N + 1):
    c = S[-i]
    if c == "?":
        for n in range(10):
            m = n * exponent % 13
            mod13[i] += np.roll(mod13[i - 1], m)
    else:
        m = int(c) * exponent % 13
        mod13[i] += np.roll(mod13[i - 1], m)
    exponent = exponent * 10 % 13
    mod13[i] %= MOD
print(mod13[N][5])

### FIXED CODE ###

def main():
    MOD = 10 ** 9 + 7
    S = input()
    N = len(S)
    mod13 = [[0] * 13 for _ in range(N + 1)]
    mod13[0][0] = 1
    exponent = 1
    for i in range(1, N + 1):
        c = S[-i]
        if c == "?":
            for n in range(10):
                m = n * exponent % 13
                for r in range(13):
                    mod13[i][(r + m) % 13] += mod13[i - 1][r]
        else:
            m = int(c) * exponent % 13
            for r in range(13):
                mod13[i][(r + m) % 13] = mod13[i - 1][r]
        exponent = exponent * 10 % 13
        for r in range(13):
            mod13[i][r] %= MOD
    print(mod13[N][5])

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

from functools import reduce
import operator

NK = list(map(int, input().split(' ')))
N = NK[0]
K = NK[1]
A_list = list(map(int, input().split(' ')))

score_list = []

score = reduce(operator.mul, A_list[0: K])
score_list.append(score)

for g in range(K, N):
    score = score / A_list[g-K] * A_list[g]
    score_list.append(score)

for i in range(len(score_list) - 1):
    if (score_list[i] < score_list[i+1]):
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

NK = list(map(int, input().split(' ')))
N = NK[0]
K = NK[1]
A = list(map(int, input().split(' ')))

for i in range(K, N):
    if (A[i-K] < A[i]):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = 10**6

# ふるって生き残ったやつがTrue
dp = [1 for i in range(amax+1)]
for num in a:
    for i in range(2, amax//num + 1): dp[num * i] = 0

# カウンター
cnt = [0 for i in range(amax+1)]
for num in a:
    cnt[num] += 1

# 生き残っていて、かつ、１回だけ登場するやつ
ans = 0
for num in a:
    if dp[num] and cnt[num]==1: ans += 1

print(ans)


### FIXED CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
from math import cos,sin,tan,sqrt
import cmath as cma
import copy as cp
import sys
import re
sys.setrecursionlimit(10**7)
EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf
MOD = 10**9 + 7

def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def adj(n): return [[] for _ in range(n)]

n = iinput()
a = iarr()
amax = max(a)
#amax = 10**6

cnt = [0 for i in range(amax+1)]
for num in a:
    for i in range(1,amax//num + 1):
        tmp = num * i
        cnt[tmp] += 1

ans = 0
for num in a:
    if cnt[num]==1: ans += 1
print(ans)
### BUGGY CODE ###

s = input()
import re
leng = len(s)


while ('01' in s) or ('10' in s):
    s = re.sub(r'01|10','', s)

print(leng-len(s))


### FIXED CODE ###

s = input()
leng = len(s)
zero = s.count('0')
one = s.count('1')
print(2*min(zero, one))
### BUGGY CODE ###

N, M = map(int, input().split())
L = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    L[a].append(b)
    L[b].append(a)

ans = [0 for _ in range(N+1)]
now = [1]
next = []

while len(now):
    for x in now:
        for y in L[x]:
            if (y not in now) and (ans[y] == 0):
                ans[y] = x
                next.append(y)
    now = next.copy()
    next = []

print("Yes")
for x in range(2, N+1):
    print(ans[x])

### FIXED CODE ###

N, M = map(int, input().split())
L = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    L[a].append(b)
    L[b].append(a)

ans = [0 for _ in range(N+1)]
now = [1]
next = []

while len(now):
    for x in now:
        for y in L[x]:
            if (ans[y] == 0) and (y not in now):
                ans[y] = x
                next.append(y)
    now = next.copy()
    next = []

print("Yes")
for x in range(2, N+1):
    print(ans[x])
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

A.sort(reverse=True)
max_value = A.pop(0)
diff = [max_value]
ans = 0
for i in A:
    ans = ans + diff.pop(0)
    diff = diff + [i, i]

print(ans)

### FIXED CODE ###

import sys
from collections import deque

N = int(sys.stdin.readline())
A = [int(i) for i in sys.stdin.readline().split(' ')]

A.sort(reverse=True)
max_value = A.pop(0)
diff = deque([max_value])
ans = 0
for i in A:
    ans = ans + diff.popleft()
    diff.append(i)
    diff.append(i)

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

S = input()
l = len(S)
ans = 0
for i in range(l - 4):
    for j in range(4, l - i + 1):
        x = int(S[i:i + j])
        if x % 2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter

S = input()
mods = [0]
num, ten = 0, 1
for n in S[::-1]:
    num += int(n) * ten
    num %= 2019
    mods.append(num)
    ten *= 10
    ten %= 2019

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

N = int(input())
P = list(map(int,input().split()))
a = 0
for i in range(N):
    hantei = 'OK'
    for j in range(i):
        if P[i] > P[j]:
            hantei = 'NG'
    if hantei == 'OK':
        a += 1
    
print(a)

### FIXED CODE ###

def main():
    N = int(input())
    P = tuple(map(int,input().split()))
    a = 1
    minP = P[0]
    for i in range(1, N):
        if minP < P[i]:
            pass
        else:
            minP = P[i]
            a += 1
    print(a)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

f=input
n,s,q=int(f()),list(f()),int(f())
L=[[] for i in range(26)]
for i in range(n):
  L[ord(s[i])-97].append(i)
from bisect import *
for i in range(q):
  a,b,c=input().split()
  b=int(b)-1
  if a=='1':
    l=L[ord(s[b])-97]
    l.pop(bisect(l,b)-1)
    s[b]=c
    insort(L[ord(c)-97],b)
  else:
    t=0
    for l in L:
      m=bisect(l,b-1)
      if m<len(l) and l[m]<int(c): t+=1
    print(t)

### FIXED CODE ###

n=int(input())
l=list(input())
q=int(input())
bit=[[0]*(n+1) for i in range(26)]
def bit_sum(o,i):
  s=0
  while i:
    s+=bit[o][i]
    i-=i&-i
  return s
def bit_add(o,i,x):
  while i<=n:
    bit[o][i] += x
    i+=i&-i
for i in range(n):
  bit_add(ord(l[i])-97,i+1,1)
for i in range(q):
  a,b,c=input().split()
  b=int(b)-1
  if a=='1':
    bit_add(ord(l[b])-97,b+1,-1)
    l[b]=c
    bit_add(ord(c)-97,b+1,1)
  else:
    c=int(c)
    print(sum(1 for o in range(26) if bit_sum(o,c)-bit_sum(o,b)))
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1])
for chenge in BC:
    B = chenge[0]; C = chenge[1]
    for i in range(B):
        if A[i] < C:
            A[i] = C
        else:
            break
    A.sort()
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x:x[1],reverse=True)
i = 0
for bc in BC:
    for _ in range(bc[0]):
        if i > len(A)-1:
            break
        if A[i] > bc[1]:
            break
        A[i] = bc[1]
        i += 1
print(sum(A))
### BUGGY CODE ###

def f(index, num):
  for k in range(13):
    a[index][(k*10+num)%13]+=a[index-1][k]

S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()
  
MOD=10**9+7

a=[[0]*13 for i in range(N)]
if S[0]=='?':
  a[0]=[1]*10+[0]*3
else:
  a[0][int(S[0])]=1

for i in range(1, N):
  if S[i]=='?':
    for j in range(10):
      f(i, j)
    for j in range(13):
      a[i][j]%=MOD
  else:
    f(i, int(S[i]))
    
print(a[-1][5])

### FIXED CODE ###

def f(index, num):
  for k in range(13):
    a[index][(k*10+num)%13]+=a[index-1][k]

S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()
  
MOD=10**9+7

a=[[0]*13 for i in range(N)]
if S[0]=='?':
  a[0]=[1]*10+[0]*3
else:
  a[0][int(S[0])]=1

for i in range(1, N):
  if S[i]=='?':
    for j in range(10):
      f(i, j)
    for j in range(13):
      a[i][j]%=MOD
  else:
    f(i, int(S[i]))
    
print(a[-1][5])