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

import bisect
from collections import deque
n, m = map(int, input().split())
A = deque(sorted(map(int, input().split())))
BC = []
for j in range(m):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
for b, c in BC:
    change = 0
    for i, a in enumerate(A):
        if i == b:
            break
        if a < c:
            change += 1
    for _ in range(change):
        A.popleft()
        A.append(c)
print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())
A = sorted(map(int, input().split()))
BC = []
for j in range(m):
    b, c = map(int, input().split())
    BC.append((b, c))
BC = sorted(BC, key=lambda x: x[1], reverse=True)
D = []
for b, c in BC:
    D.extend([c for i in range(b)])
    if len(D) >= n:
        D = D[:n]
        break
for x in range(len(D)):
    if A[x] > D[x]:
        break
else:
    x += 1
print(sum(A[x:]) + sum(D[:x]))
### BUGGY CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

T = S()

def match(v):
    return int(v) % 2019 == 0

cnt = 0

M = {}
X = []
for i in range(0, len(T)):
    for j in range(i+1, len(T)+1):
        s = T[i:j]
        if s in M:
            cnt += 1
            continue

        if s in X:
            continue

        if match(s):
            M[s] = True
            cnt += 1
        X.append(s)

print(cnt)

### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

T = S()

revT = reversed(T)

n, d, mods = 0, 1, [1]+[0]*2019

for i in revT:
    n = (n + int(i)*d)%2019
    d = d*10%2019
    mods[n] += 1

sum = 0
for j in mods:
    sum += j*(j-1)//2

print(sum)
### BUGGY CODE ###

import math
K = int(input())
K +=1
ans = 0
for i in range(1,K):
  for j in range(1,K):
    for k in range(1,K):
      ans += math.gcd(math.gcd(i,j),k)
print(ans)

### FIXED CODE ###

import math
K = int(input())
K +=1
ans = 0
for i in range(1,K):
  ans += math.gcd(i,i)
  for j in range(i+1,K):
    ans += 6 * math.gcd(i,j)
    for k in range(j+1,K):
      ans += 6 * math.gcd(math.gcd(i,j),k)

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

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
h = tuple(map(int,input().split()))

dp = [0] + [float("inf")]*(n-1)
for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[n-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
h = tuple(map(int,input().split()))

dp = [0] + [float("inf")]*(n-1)
for i in range(1,n):
    for j in range(max(0,i-k),i):
        dp[i] = min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])
### BUGGY CODE ###

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

cost = [0] + [float("inf")] * (N-1)

for i in range(1, N):
    for back in range(1, K+1):
        try:
            cost[i] = min(cost[i], cost[i-back] + abs(h[i] - h[i-back]))
        except IndexError:
            break

print(cost[-1])

### FIXED CODE ###

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

cost = [0] + [float("inf")] * (N-1)

for i in range(1, N):
    for back in range(1, K+1):
        try:
            cost[i] = min(cost[i], cost[i-back] + abs(h[i] - h[i-back]))
        except IndexError:
            break

print(cost[-1])
### BUGGY CODE ###

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

dictA = {}

for z in A:
    dictA.setdefault(z, 0)
    dictA[z] += 1


BC = [list(map(int, input().split())) for i in range(Q)]
for x in BC:
    if x[0] in dictA:
        dictA.setdefault(x[1], 0)
        dictA[x[1]] += dictA[x[0]]
        del dictA[x[0]]

    sumA = 0
    for k, v in dictA.items():
        sumA += k * v
    print(sumA)


### FIXED CODE ###

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

dictA = {}

for z in A:
    dictA.setdefault(z, 0)
    dictA[z] += 1

sumA = sum(A)

BC = [list(map(int, input().split())) for i in range(Q)]
for x in BC:
    if x[0] in dictA.keys():
        sumA += (x[1] - x[0]) * dictA[x[0]]
        dictA.setdefault(x[1], 0)
        dictA[x[1]] += dictA[x[0]]
        dictA.pop(x[0])
    print(sumA)
### BUGGY CODE ###

r,g,b,n = map(int, input().split())

ans = 0
for i in range(n//r+1):
  for j in range(n//g+1):
    if n - (r*i + g*j) >= 0 and (n - (r*i + g*j)) % b == 0: ans += 1
print(ans)

### FIXED CODE ###

from math import ceil
r,g,b,n = map(int, input().split())

ans = 0
for i in range(ceil(n/r)+1):
  for j in range(ceil(n/g)+1):
    if n - (r*i + g*j) >= 0 and (n - (r*i + g*j)) % b == 0: ans += 1
print(ans)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(M)]

heapq.heapify(a)

for b, c in bc:
    for i in range(b):
        hq = heapq.heappop(a)
        if hq < c:heapq.heappush(a, c)
        else:
            heapq.heappush(a, hq)
            break
print(sum(a))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(M)]

bc.sort(key=lambda x:-x[1])
cnt = True

heapq.heapify(a)

for b, c in bc:
    if not cnt: break
    for i in range(b):
        hq = heapq.heappop(a)
        if hq < c:heapq.heappush(a, c)
        else:
            heapq.heappush(a, hq)
            cnt = False
            break
print(sum(a))
### BUGGY CODE ###

N, K = map(int, input().split())
while N > K//2:
  N = abs(N-K)
print(N)

### FIXED CODE ###

N, K = map(int, input().split())
a = (N//K) * K
N -= a
while N > K//2:
  N = abs(N-K)
print(N)
### BUGGY CODE ###

from bisect import bisect

a, b, q = map(int, input().split())
s = [int(input()) for i in range(a)]
t = [int(input()) for i in range(b)]
x = [int(input()) for i in range(q)]

sentinel = lambda x: [-9e20] + x + [9e20]
s = sentinel(s)
t = sentinel(t)

for i in x:
    ss = bisect(s, i)
    tt = bisect(t, i)

    ll = max(s[ss], t[tt]) - i
    rr = i - min(s[ss-1], t[tt-1])
    rl = min((s[ss]- i) + s[ss] - t[tt-1], (t[tt]- i) + t[tt] - s[ss-1])
    lr = min((i - s[ss-1]) + t[tt] - s[ss-1], (i - t[tt-1]) + s[ss] - t[tt-1])

    print(min(ll, rr, rl, lr))

### FIXED CODE ###

import bisect
 
a, b, q = map(int, input().split())
s = sorted([int(input()) for i in range(a)])
t = sorted([int(input()) for i in range(b)])

s = [-9e20] + s + [9e20]
t = [-9e20] + t + [9e20]
 
for i in range(q):
    x = int(input())
    p = bisect.bisect_left(s,x)
    m = bisect.bisect_left(t,x)
    
    ll = max(s[p], t[m]) - x
    lr = min(s[p] * 2 - t[m-1] - x, t[m] * 2 - s[p-1] - x)
    rl = min(s[p] - t[m-1] * 2 + x, t[m] - s[p-1] * 2 + x)
    rr = x - min(s[p-1], t[m-1])

    print(min(ll, lr, rl, rr))
### BUGGY CODE ###

line1 = input()
line2 = input()
num_list = line2.split(" ")
flag = 0

for i in range(len(num_list)-1):
    search_num = num_list[0]
    num_list.pop(0)
    if search_num in num_list:
        flag = 1
        break
if flag == 1:
    print("NO")
else:
    print("YES")
        

### FIXED CODE ###

line1 = input()
line2 = input()
num_list = line2.split(" ")

if len(num_list) == len(set(num_list)):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys
s = input()
gx,gy = map(int, input().split(' '))
x_d = [0]
y_d = []
cnt = 0
for i in range(len(s)):
    if s[i] == "T":
        cnt += 1
        if cnt % 2 == 0:
            x_d.append(0)
        elif cnt % 2 == 1:
            y_d.append(0)
    if s[i] == "F":
        if cnt % 2 == 0:
            x_d[-1] += 1
        elif cnt % 2 == 1:
            y_d[-1] += 1
gx -= x_d[0]
x_d[0] = 0
x_d.append(0)
y_d.append(0)
if (sum(x_d)-gx) % 2 or (sum(y_d)-gy) % 2 or sum(x_d) < abs(gx) or sum(y_d) < abs(gy):
    print("No")
    sys.exit()
x_n = (sum(x_d)-gx)//2
y_n = (sum(y_d)-gy)//2
DPx = [[False for i in range(x_n+2)] for j in range(len(x_d))]
DPy = [[False for i in range(y_n+2)] for j in range(len(y_d))]
for x in DPx:
    x[0] = True
for y in DPy:
    y[0] = True
for i in range(len(x_d)-1):
    for j in range(x_n+1):
        if DPx[i][j]:
            DPx[i+1][j] = True
            if j+x_d[i] <= x_n+1:
                DPx[i+1][j+x_d[i]] = True
for i in range(len(y_d)-1):
    for j in range(y_n+1):
        if DPy[i][j]:
            DPy[i+1][j] = True
            if j+y_d[i] <= y_n+1:
                DPy[i+1][j+y_d[i]] = True
if DPx[len(x_d)-1][x_n] and DPy[len(y_d)-1][y_n]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import sys
s = input()
gx,gy = map(int, input().split(' '))
x_d = [0]
y_d = []
cnt = 0
for i in range(len(s)):
    if s[i] == "T":
        cnt += 1
        if cnt % 2 == 0:
            x_d.append(0)
        elif cnt % 2 == 1:
            y_d.append(0)
    if s[i] == "F":
        if cnt % 2 == 0:
            x_d[-1] += 1
        elif cnt % 2 == 1:
            y_d[-1] += 1
gx -= x_d[0]
x_d[0] = 0
x_d.append(0)
y_d.append(0)
if (sum(x_d)-gx) % 2 or (sum(y_d)-gy) % 2 or sum(x_d) < abs(gx) or sum(y_d) < abs(gy):
    print("No")
    sys.exit()
x_n = (sum(x_d)-gx)//2
y_n = (sum(y_d)-gy)//2
DPx = [[False for i in range(x_n+2)] for j in range(len(x_d))]
DPy = [[False for i in range(y_n+2)] for j in range(len(y_d))]
for x in DPx:
    x[0] = True
for y in DPy:
    y[0] = True
for i in range(len(x_d)-1):
    for j in range(x_n+1):
        if DPx[i][j]:
            DPx[i+1][j] = True
            if j+x_d[i] <= x_n+1:
                DPx[i+1][j+x_d[i]] = True
for i in range(len(y_d)-1):
    for j in range(y_n+1):
        if DPy[i][j]:
            DPy[i+1][j] = True
            if j+y_d[i] <= y_n+1:
                DPy[i+1][j+y_d[i]] = True
if DPx[len(x_d)-1][x_n] and DPy[len(y_d)-1][y_n]:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

def gcd(a, b, c):
    r = 1
    for i in range(min(a, b, c) + 1):
        i += 1
        if a % i == 0 and b % i == 0 and c % i == 0:
            r = i
    return r

v = int(input())
sum = 0

for i in range(v):
    i += 1
    for j in range(v):
        j += 1
        for k in range(v):
            k += 1
            sum += gcd(i, j, k)

print(sum)

### FIXED CODE ###

from math import gcd

v = int(input())
sum = 0

for i in range(1, v + 1):
    for j in range(1, v + 1):
        for k in range(1, v + 1):
            sum += gcd(gcd(i, j), k)

print(sum)
### BUGGY CODE ###

N = int(input())
l = [-1] * N

def get(v1, v2):
    print(v1)
    s = input()
    if s=="Male":
        l[v1] = 0
    elif s=="Female":
        l[v1] = 1
    else:
        exit()

    print(v2)
    s = input()
    if s=="Male":
        l[v2] = 0
    elif s=="Female":
        l[v2] = 1
    else:
        exit()
    
    return l[v2]==l[v1]


left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2
    v = get(left, mid)
    if (v==True and (mid-left)%2) or (v==False and (mid-left)%2==0):
        left, right = left+1, m-1
    else:
        left, right = m+1, right-1


### FIXED CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right
### BUGGY CODE ###

def main():
    n, s = map(int, input().split())
    mod = 998244353
    a = list(map(int, input().split()))
    dp = [[0]*(s+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(1, n+1):
        ai = a[i-1]
        di = dp[i]
        dio = dp[i-1]
        for j in range(s+1):
            di[j] += 2*dio[j]
            di[j] %= mod
            if j >= ai:
                di[j] += dio[j-ai]
                di[j] %= mod
        dp[i] = di
    print(dp[n][s])
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, s = map(int, input().split())
    mod = 998244353
    a = list(map(int, input().split()))
    dp = [[0]*(s+1) for _ in range(n+1)]
    dp[0][0] = 1
    dio = dp[0]
    for i in range(1, n+1):
        ai = a[i-1]
        di = dp[i]
        for j in range(min(s+1, ai)):
            di[j] = (di[j]+2*dio[j])%mod
        for j in range(ai, s+1):
            di[j] = (di[j]+2*dio[j]+dio[j-ai])%mod
        dp[i] = di
        dio = di
    print(dp[n][s])
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)

#再帰を使って各ノードのカウンタの値を決定
def dfs(v,p):
    for u in G[v]:
        if u!=p:
            c[u]+=c[v]
            dfs(u,v) 
N,Q = list(map(int,input().split()))

G=[]
for i in range(N):
    G.append([])
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

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

dfs(0,-1)

ans = ' '.join([str(x) for x in c])

print(ans)

### FIXED CODE ###

'''
pythonの再帰は10^5timesですら厳しい
import sys
sys.setrecursionlimit(10000000)

def dfs(v,p,G,c):
    for u in G[v]:
        if u!=p:
            c[u]+=c[v]
            dfs(u,v,G,c) 
'''
from collections import deque

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

G=[]
for i in range(N):
    G.append([])
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)

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

stack=deque([0])
parent = [-1]*N

while(stack):
    v = stack.pop()
    for u in G[v]:
        if u!=parent[v]:
            c[u]+=c[v]
            parent[u]=v
            stack.appendleft(u)


ans = ' '.join([str(x) for x in c])

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

N = int(input())
A = list(map(int,input().split()))
#A.sort(reverse = True)
Al=list(set(A))
Al.sort(reverse = True)
HW = []
for i in Al:
  n = A.count(i)
  for j in range(min(n//2,2)):
    HW.append(i)
  if len(HW)>=2:
    break
HW = HW + [0,0]
print(HW[0]*HW[1])

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
A.sort(reverse = True)
HW = []
i = 1
while i<N:
  if A[i]==A[i-1]:
    n = A.count(A[i])
    HW += [A[i]]*(min(n//2,2))
    i = i + n -1
  else:
    i = i + 1
  if len(HW)>=2:
    break
if len(HW)<2:
  print(0)
else:
  print(HW[0]*HW[1])
### BUGGY CODE ###

def is_match(str_num):
  for idx, num in nums.items():
    if str_num[idx] != num: return False
  return True

S = input()
lenS = len(S)
nums = {idx: s for idx, s in enumerate(S) if s != '?' }

MOD = 10**9 + 7
ans = 0

for i in range(int(S.replace('?', '9'))//13 + 1):
  num = i*13 + 5
  str_num = str(num).zfill(lenS)

  if is_match(str_num) is True:
    ans += 1
    ans = ans % MOD

print(ans%MOD)

### FIXED CODE ###

MOD1 = 13
MOD2 = 10 ** 9 + 7

S = input()
N = len(S)
dp = [[0 for _ in range(MOD1)] for _ in range(N)]

if S[0] == '?':
    for k in range(10):
        dp[0][k % MOD1] += 1
else:
    dp[0][int(S[0]) % MOD1] += 1

for i in range(N-1):
    if S[i+1] == '?':
        for j in range(MOD1):
            for k in range(10):
                tmp_j = (j * 10 + k) % MOD1
                dp[i+1][tmp_j] += dp[i][j]
                dp[i + 1][tmp_j] %= MOD2
    else:
        for j in range(MOD1):
            tmp_j = (j * 10 + int(S[i+1])) % MOD1
            dp[i+1][tmp_j] += dp[i][j]
            dp[i + 1][tmp_j] %= MOD2

print(dp[-1][5] % MOD2)
### BUGGY CODE ###

X, Y = map(int, input().split())
ans = X
while ans <=10**18:
  if ans % Y != 0:
    print(ans)
    exit()
  else:
    ans += X
print(-1)

### FIXED CODE ###

X, Y = map(int, input().split())
if X % Y == 0:
  print(-1)
else:
  print(X)
### BUGGY CODE ###

def rec(x1,q):
    return x1-((x1**3-q)/(3*(x1**2)))

q = []
while True:
    try:
        tmp = int(input())
        if tmp == -1:
            break
        q.append(tmp)
    except EOFError:
        break
for i in range(len(q)):
    x1 = float(q[i]/2)
    for j in range(500000):
        x1 = rec(x1,q[i])
    print(x1)

### FIXED CODE ###

def rec(x1,q):
    return x1-((x1**3-q)/(3*(x1**2)))

q = []
while True:
    try:
        tmp = int(input())
        if tmp == -1:
            break
        q.append(tmp)
    except EOFError:
        break
for i in range(len(q)):
    x1 = float(q[i]/2)
    while True:
        x1 = rec(x1,q[i])
        if abs(x1**3 - q[i]) < 0.00001*q[i]:
            break
    print(x1)
### BUGGY CODE ###

N=int(input())
A=[i for i in input().split()]
s=[A[0]]
if N%2==1:
    for i in range(1,N):
        if i%2==1:
            s=s+[A[i]]
        else:
            s=[A[i]]+s
else:
    for i in range(1,N):
        if i%2==0:
            s=s+[A[i]]
        else:
            s=[A[i]]+s 
print(' '.join(map(str,s)))

### FIXED CODE ###

from collections import deque
N=int(input())
A=[i for i in input().split()]
s=deque()
s.append(A[0])
if N%2==1:
    for i in range(1,N):
        if i%2==1:
            s.append(A[i])
        else:
            s.appendleft(A[i])
else:
    for i in range(1,N):
        if i%2==0:
            s.append(A[i])
        else:
            s.appendleft(A[i])
print(' '.join(map(str,s)))
### BUGGY CODE ###

from heapq import (
    heapify,  # 優先度付きキューの生成
    heappop,  # キューから値を取り出す
    heappush,   # キューに値を格納
    heappushpop,   # push -> popの順
    heapreplace,   # pop -> pushの順
    )

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-i for i in A]

bc = []
for _ in range(M):
    B, C = map(int, input().split())
    bc.extend([-C]*B)

A = A + bc
heapify(A)
total = 0

for _ in range(N):
    total += -heappop(A)

print(total)

### FIXED CODE ###

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

dic = {}
for i in range(N):
    tmp = A[i]
    if tmp in dic:
        dic[tmp] += 1
    else:
        dic[tmp] = 1

for _ in range(M):
    B, C = map(int, input().split())
    if C in dic:
        dic[C] += B
    else:
        dic[C] = B

dic = sorted(dic.items(), reverse=True)

ans, cnt = 0, 0
i = 0
while True:
    k, v = dic[i]
    cnt += v
    if cnt < N:
        ans += k*v
    elif cnt == N:
        ans += k*v
        break
    else:
        ans += k*(v - (cnt-N))
        break
    i += 1

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

S=str(input())
ans=0
while S.find('ST')!= -1:
    S=S.replace('ST','')

print(len(S))

### FIXED CODE ###

S=list(str(input()))
ans=[]
for i in S:
    if i=='S':
        ans.append(i)
    elif i=='T' and len(ans)==0:
        ans.append(i)
    elif i=='T' and ans[-1]=='T':
        ans.append(i)
    elif i=='T' and ans[-1]=='S':
        del ans[-1]
print(len(ans))
### BUGGY CODE ###

n, k = list(map(int,input().split()))
l = list(map(int,input().split()))
dp = [0]*n
dp[1] = abs(l[0] - l[1])
for i in range(2,n):
    tem = []
    for j in range(i-1,max(0,i-k)-1,-1):
        tem.append(dp[j] + abs(l[i] - l[j]))
    dp[i] = min(tem)
    
print(dp[n-1])
    
    

### FIXED CODE ###

n, k = list(map(int,input().split()))
l = list(map(int,input().split()))
dp = [10**9]*n
dp[0] = 0
dp[1] = abs(l[0] - l[1])
for i in range(2,n):
    for j in range(i-1,max(0,i-k)-1,-1):
        tem = dp[j] + abs(l[i] - l[j])
        if tem<dp[i]:
            dp[i] = tem
    
print(dp[n-1])
### BUGGY CODE ###

H,W = map(int,input().split())
A = [input() for _ in range(H)]
C = [-1,1]
ans = [[1000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0

while True:
    count = 0
    for i in range(H):
        for j in range(W):
            if ans[i+1][j+1] >= 1000:
                count += 1
                num = min(ans[i+1][j],ans[i+1][j+2],ans[i][j+1],ans[i+2][j+1])+1
                ans[i+1][j+1] = num
    if count==0:
        break
num = 0
for i in range(H):
    for j in range(W):
        num = max(num,ans[i+1][j+1])

print(num)

### FIXED CODE ###

H,W = map(int,input().split())
A = [input() for _ in range(H)]
ans = [[10000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0

for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)

num = 0
for i in range(H):
    for j in range(W):
        num = max(num,ans[i+1][j+1])

print(num)
### BUGGY CODE ###

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

#dp[i]:i番目に到達するまでにはらうコストの最小値
INF = float('inf')
dp = [0 for i in range(N)]

for i in range(1,N):
    cost_min = INF
    for k in range(1,i+1):
        if k <= K:
            cost = dp[i-k] + abs(h[i]-h[i-k])
            cost_min = min(cost, cost_min)
        else:
            break
    dp[i] = cost_min


print(dp[N-1])

### FIXED CODE ###

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

#dp[i]:i番目に到達するまでにはらうコストの最小値
INF = float('inf')
dp = [INF for i in range(N)]
dp[0] = 0

for i in range(0,N):
    for k in range(1, K+1):
        if i+k > N-1:
            break
        dp[i+k] = min(dp[i+k], dp[i]+abs(h[i+k]-h[i]))


print(dp[N-1])
### BUGGY CODE ###

N = int(input())
ab = [list(map(int, input().split())) for i in range(N)]
ab = sorted(ab, key=lambda x: x[1])
for i in range(N):
    for j in range(i, N):
        ab[j][1] -= ab[i][0]
        if ab[j][1] < 0:
            print("No")
            exit()
    ab = ab[:i] + sorted(ab[i:], key=lambda x: x[1])

print("Yes")


### FIXED CODE ###

N = int(input())
ab = [[0, 0]] + [list(map(int, input().split())) for i in range(N)]
ab = sorted(ab, key=lambda x: x[1])
for i in range(len(ab) - 1):
    ab[i + 1][0] += ab[i][0]
    if ab[i + 1][1] < ab[i + 1][0]:
        print("No")
        exit()

print("Yes")
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
#S = S_raw.replace('AC', 'XC')
l = [0] * Q
r = [0] * Q

for i in range(Q):
    l[i], r[i] = map(int, input().split())
#    print(l[i], r[i])

for i in range(Q):
    sub_str = S[l[i]-1:r[i]]
    print(sub_str.count('AC'))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)

for i in range(N):
    t[i + 1] = t[i] + (1 if S[i: i + 2] == 'AC' else 0)
#    print(t[i])

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

s = input()
c = 0
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        if int(s[i:j])%2019 == 0:
            c+=1
print(c)

### FIXED CODE ###

s = input()
len_s = len(s)
pre = 0
mod = [0]*2019
mod[0]=1
x = 1
for i in range(len_s):
    pre = (x*int(s[len_s-i-1])+pre)%2019
    mod[pre] += 1
    x *= 10
    x %= 2019
print(sum([m*(m-1)//2 for m in mod]))