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

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    N+=2
    H=[0]+list(map(int,input().split()))+[0]
    edge=[[] for _ in range(N*(K+1))]
    for i in range(N):
        for j in range(K+1):
            for k in range(K+1-j):
                if i+k+1<N:
                    edge[i*(K+1)+j].append((max(H[i+k+1]-H[i],0),(i+k+1)*(K+1)+j+k))
    from heapq import heappop,heappush
    def dijkstra(start,n,edges):
        d=[INF]*n
        used=[False]*n
        d[start]=0
        used[start]=True
        edgelist=[]
        for edge in edges[start]:
            heappush(edgelist,edge)
        while edgelist:
            minedge=heappop(edgelist)
            if used[minedge[1]]:
                continue
            v=minedge[1]
            d[v]=minedge[0]
            used[v]=True
            for edge in edges[v]:
                if not used[edge[1]]:
                    heappush(edgelist,(edge[0]+d[v],edge[1]))
        return d
    d=dijkstra(0,N*(K+1),edge)
    print(min(d[(N-1)*(K+1):]))

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,K=map(int,input().split())
    N+=1
    H=[0]+list(map(int,input().split()))+[0]
    dp=[[INF]*(K+1) for _ in range(N+1)]
    dp[0][0]=0
    for i in range(N):
        for j in range(K+1):
            for k in range(j,K+1):
                if i-(k-j)>=0:
                    dp[i+1][k]=min(dp[i+1][k],dp[i-(k-j)][j]+max(H[i+1]-H[i-(k-j)],0))
                    pass
    print(dp[-1][-1])

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

n, k = map(int, input().split())
a = list(map(lambda x:int(x)%k, input().split()))

b = 0
c = 0
for i in range(1,min(n,k-1)+1):
  c = (c + a[i-1])%k
  c2 = c
  for j in range(n-i+1):
    c2 = c2%k
    if c2 == i:
      b += 1
    if i+j < n:
      c2 += a[i+j] - a[j]
print(b)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
a[0] = (a[0]-1)%k
for i in range(1,n):
  a[i] = (a[i]+a[i-1]-1)%k
ans = 0
b = {0:1}
for i in range(n):
  if i>0:
    b[a[i-1]] = b.get(a[i-1],0) + 1
  if i>=k:
    b[a[i-k]] -= 1
  if i==k-1:
    b[0] -= 1
  ans += b.get(a[i],0)
print(ans)
### BUGGY CODE ###

from itertools import permutations, product
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

iwakan_min = 500001

def modthree(i, j):
	if (i + j) % 3 == 0:
		return p
	elif (i + j) % 3 == 1:
		return q
	else:
		return r

for p, q, r in permutations(range(0, C), r=3):
	iwakan = 0
	for i, j in product(range(N), repeat=2):
		iwakan += D[c[i][j] - 1][modthree(i, j)]
	if iwakan < iwakan_min:
		iwakan_min = iwakan

print(iwakan_min)

### FIXED CODE ###

from itertools import permutations, product
from collections import Counter
N, C = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(C)]
c = [list(map(int, input().split())) for _ in range(N)]

zero = []
one = []
two = []
for i, j in product(range(N), repeat=2):
	if (i + j) % 3 == 0:
		zero.append(c[i][j])
	elif (i + j) % 3 == 1:
		one.append(c[i][j])
	else:
		two.append(c[i][j])

zero = Counter(zero)
one = Counter(one)
two = Counter(two)

iwakan_min = float("inf")

for p, q, r in permutations(range(0, C), r=3):
	iwakan = 0
	for key, value in zero.items():
		iwakan += value * (D[key - 1][p])
	for key, value in one.items():
		iwakan += value * (D[key - 1][q])
	for key, value in two.items():
		iwakan += value * (D[key - 1][r])
	if iwakan < iwakan_min:
		iwakan_min = iwakan

print(iwakan_min)
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

L = []

for i in range(len(A)):
    for j in range(len(B)):
        L.append(A[i] + B[j])

L.sort(reverse=True)

ans_list = [0] * (10000000)

for i in range(min(K,len(L))):
    for j in range(len(C)):
        ans_list.append(L[i] + C[j])

ans_list.sort(reverse=True)


for i in range(K):
    print(ans_list[i])

### FIXED CODE ###

#%%
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort()
b.sort()
c.sort()

bc = [0] * (y * z)
q = 0
for i in range(y):
    for j in range(z):
        bc[q] = b[i] + c[j]
        q += 1

bc.sort(reverse=True)
r = len(bc)
bc = bc[:min(k, r)]

abc = [0] * (x * min(k, r))
q = 0
for i in range(min(k, r)):
    for j in range(x):
        abc[q] = bc[i] + a[j]
        q += 1

abc.sort(reverse=True)
for i in range(min(k, x*y*z)):
    print(abc[i])
### BUGGY CODE ###

def Maximum_Profit(A,N):
    Max = A[1]-A[0]
    for i in range(N-1):
        for j in range(i+1,N):
            if (A[j]-A[i]) > Max :
                Max = A[j]-A[i]
    return Max

N = int(input())
A = [] 
for i in range (N):
    A.append(input())
A = list(map(int,A))
print(Maximum_Profit(A,N))


### FIXED CODE ###

n = int(input())
numbers = []

minv = int(input())
num = int(input())

max_r = num - minv

if(minv > num):
    minv = num

for i in range(2,n):
    num = int(input())
    if(max_r <(num - minv)):
        max_r = num - minv

    if(minv > num):
        minv = num

print(max_r)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
if True:
    n,x,y = map(int, input().split())


else:
    # n=5
    # x=2
    # y=4
    # n=3
    # x=1
    # y=3
    n=7
    x=3
    y=7

# print(n)
# print(x)
# print(y)
#
ret = [0] * (n-1)
for i in range(1, n):
    for j in range(i+1, n+1):
        # print(str(i) + "," + str(j))
        p =[]
        p.append(j - i)
        p.append(abs(i - x) + 1 + abs(j - y))
        p.append(abs(i - y) + 1 + abs(j - x))

        # print(p)
        # print(min(p))
        ret[min(p)-1] += 1

# print(ret)
# print("=======")
for data in ret:
    print(data)

### FIXED CODE ###

n,x,y = map(int, input().split())

ret = [0] * (n-1)
for i in range(1, n):
    for j in range(i+1, n+1):
        p1 = j-i
        p2 = abs(i - x) + 1 + abs(j - y)
        p3 = abs(i - y) + 1 + abs(j - x)
        if p1 > p2:
            p1 = p2
        if p1 > p3:
            p1 = p3
        ret[p1-1] += 1

for data in ret:
    print(data)
### BUGGY CODE ###

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

ans_set=set(a)

i=0
while(i<len(a)):
    if(a[i] in ans_set):
        j=i+1
        while(j<len(a)):
            if(a[j] in ans_set and a[j]%a[i]==0):
                ans_set.remove(a[j])
                del a[j]
                j-=1
            j+=1
    i+=1
#print(ans_set)
print(len(ans_set))


### FIXED CODE ###

import numpy as np
n=int(input())
a=sorted(list(map(int,input().split())))

dp=np.array([0 for _ in range(max(a)+1)])
for i in range(n):
    ai=a[i]
    if(dp[ai]>=2):
        continue

    j=1
    while(ai*j<=a[-1]):
        dp[ai*j]+=1
        j+=1

print(sum(dp[ai]==1 for ai in a))
### BUGGY CODE ###

X=input().split()
N=int(X[0])
M=int(X[1])
A=[]
B=[]
C=[]
count=0
for i in range(M):
 Y=input().split()
 a=int(Y[0])
 b=int(Y[1])
 A.append(a) 
 B.append(b) 
for i in range(M):
 if(A[i]==1):
   C.append(B[i])
n=len(C)
for i in range(n):
 for j in range(M):
  if((C[i]==A[j])and(B[j]==N)): 
   count +=1
if(count==0):
 print("IMPOSSIBLE")
else:
 print("POSSIBLE")

### FIXED CODE ###

N,M = map(int,input().split())
judge = 0 #0:不可,1:可

if(M >= 2):
 #リスト 島1~a間に定期便あり:1,なし:0
 island1 = [0]*N
 #リスト 島b~N間に定期便あり:1,なし:0
 islandN = [0]*N

 for i in range(M):
  a,b = map(int,input().split())
  a,b = a-1,b-1
  if(a == 0): island1[b] = 1
  if(b == 0): island1[a] = 1 
  if(a == N-1): islandN[b] = 1
  if(b == N-1): islandN[a] = 1
    
 for i in range(len(island1)):
  if((island1[i] == 1)and(islandN[i] == 1)):
    judge = 1
    break
    
if(judge == 0):
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')
### BUGGY CODE ###

N,M=map(int,input().split())
count=0
A=[i for i in range(1,N+1)]
for i in range(M):
    l,r=map(int,input().split())
    A=[j for j in range(l,r+1) if j in A]
print(len(A))

### FIXED CODE ###

N,M=map(int,input().split())
ml=0
mh=N
for i in range(M):
    l,r=map(int,input().split())
    ml=max(ml,l)
    mh=min(mh,r)
print(max(0,mh-ml+1))
### BUGGY CODE ###

s = input()
len_s = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 13 for i in range(len_s)]
if s[-1] == '?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(s[-1])] = 1

digits = 1
for i in range(1, len_s):
    digits = digits * 10
    for j in range(13):

        if dp[i - 1][j] > 0:
            if s[-(i + 1)] != '?':
                add = int(s[-(i + 1)]) * digits
                dp[i][(j + add)%13] = (dp[i][(j + add)%13] + dp[i - 1][j])%mod
            else:
                for k in range(10):
                    # k:先頭に加える数字
                    add = k * digits
                    dp[i][(j + add) % 13] = (dp[i][(j + add) % 13] + dp[i - 1][j]) % mod

print(dp[-1][5] % mod)

### FIXED CODE ###

s=input()
len_s=len(s)
mod=10**9+7
dp=[[0]*13 for i in range(len_s)]

if s[-1]!='?':
    dp[0][int(s[-1])%13]=1
else:
    for i in range(10):
        dp[0][i]=1

a=1
for i in range(1,len_s):
    a=10*a%13
    if s[-(i+1)]!='?':
        temp_S=int(s[-(i+1)])
        amari=(temp_S*a)%13
        for j in range(13):
            dp[i][(amari+j)%13]+=dp[i-1][j]%mod

    else:
        for k in range(10):
            amari=(k*a)%13
            for l in range(13):
                dp[i][(amari+l)%13]+=dp[i-1][l]%mod
#print(*dp,sep='\n')
print(dp[-1][5]%mod)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for n in range(N)]

for n in range(N):
  tmp = A.copy()
  tmp.pop(n)
  print(max(tmp))

### FIXED CODE ###

N = int(input())
A = [int(input()) for n in range(N)]
tmp = A.copy()
A.sort()
fir, sec = A[N-1], A[N-2]
for n in range(N):
  if tmp[n] == fir:
    print(sec)
  else:
    print(fir)
### BUGGY CODE ###

#-*-coding:utf8;-*-
#qpy:3
#qpy:console
n = int(input())
hp = list(map(int, input().split()))
while len(hp) != 1:
    minhp = min(hp)
    hp = [i % minhp if not i == minhp else i for i in hp]
    hp = [i for i in hp if not i == 0]
    
print(minhp)


### FIXED CODE ###

#-*-coding:utf8;-*-
#qpy:3
#qpy:console
n = int(input())
hp = list(map(int, input().split()))
while len(hp) != 1:
    minhp = min(hp)
    hp = [i % minhp if not i == minhp else i for i in hp]
    hp = [i for i in hp if not i == 0]
    if min(hp) == 1:
        minhp = min(hp)
        break
    elif hp == [minhp for i in hp]:
        break
print(minhp)
### BUGGY CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from heapq import heappush, heappop


def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF] * n
    visited = [False] * n

    dist[start] = 0
    que = [(0, start)]

    while que:
        cost, cur = heappop(que)
        if visited[cur]:
            continue

        visited[cur] = True

        for edgecost, nextnode in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))

    return dist

n, m = li()

edges = []
ins = [[] for _ in range(n)]
ots = [[] for _ in range(n)]

for _ in range(m):
    u,v = li_()
    ins[v].append(u)
    ots[u].append(v)
    edges.append((u, v))

graph = [set() for _ in range(n)]

for ui, vi in edges:
    for st in ins[ui]:
        for to in ots[vi]:
            graph[st].add((1,to))

s, t = li_()
INF = 10**8+1

dist = dijkstra(graph, s, INF)

print(-1 if dist[t] == INF else dist[t])

### FIXED CODE ###

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


from heapq import heappush, heappop

def dijkstra(graph: list, start, INF=float('inf')) -> list:
    n = len(graph)
    dist = [INF ] *n
    visited = [False ] *n

    dist[start] = 0
    que = [(0, start)]

    while que:
        cost, cur = heappop(que)

        if visited[cur]:
            continue

        visited[cur] = True

        for nextnode, edgecost in graph[cur]:
            nextcost = cost + edgecost
            if nextcost < dist[nextnode]:
                dist[nextnode] = nextcost
                heappush(que, (nextcost, nextnode))

    return dist


n, m = li()

graph = [[] for _ in range(3*n)]
for _ in range(m):
    u, v = li_()
    for i in range(3):
        graph[i*n + u].append([(i+1)%3 * n + v, 1])

s, t = li_()
INF = 1<<62
dist = dijkstra(graph, s, INF)

print(-1 if dist[t] == INF else dist[t] // 3)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort(reverse=True)
B=[int(x) for x in input().split()]
B.sort(reverse=True)
C=[int(x) for x in input().split()]
C.sort(reverse=True)
D=[a+b for a in A for b in B]
D.sort(reverse=True)
D=D[:3000]
E=[ab+c for ab in D for c in C]
E.sort(reverse=True)
for i in range(K):
  print(E[i])

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort(reverse=True)
B=[int(x) for x in input().split()]
B.sort(reverse=True)
C=[int(x) for x in input().split()]
C.sort(reverse=True)
D=[a+b for a in A for b in B]
D.sort(reverse=True)
D=D[:3000]
E=[ab+c for ab in D for c in C]
E.sort(reverse=True)
for i in range(K):
  print(E[i])
### BUGGY CODE ###

import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    dp = [[0 for _ in range(13)] for _ in range(2)]
    MOD = 10**9+7
    dp[0][0] = 1
    now,use = 0,1
    
    for i in range(l):
        for j in range(13):
            if s[i] != "?":
                num = int(s[i])
                dp[use][(j*10+num)%13] += dp[now][j]
            else:
                for k in range(10):
                    dp[use][(j*10+k)%13] += dp[now][j]
            dp[use][j] %= MOD
        dp[now] = [0 for _ in range(13)]
        now,use = use,now
    
    print(dp[now][5]%MOD)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
#input = sys.stdin.buffer.readline

def main():
    s = str(input())
    l = len(s)
    ans = [0 for _ in range(13)]
    MOD = 10**9+7
    ans[0] = 1
    
    for st in s:
        dp = [0 for _ in range(13)]
        for i in range(13):
            dp[(10*i)%13] = ans[i]%MOD
        dp += dp
        if st != "?":
            for i in range(13):
                num = int(st)
                ans[i] = dp[i+13-num]
        else:
            for i in range(13):
                ans[i] = sum(dp[i+4:i+14])
    
    print(ans[5]%MOD)

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

#coding:utf-8

from collections import defaultdict
import itertools

if __name__ == "__main__":
    N, W = map(int, raw_input().split(" "))

    items = defaultdict(list)
    item_num = defaultdict(int)
    for i in range(N):
        w, v = map(int, raw_input().split(" "))
        if i == 0:
            w_list = range(w, w + 4)
        items[w].append(v)
        item_num[w] += 1

    for k in items.keys():
        items[k].sort(reverse = True)

    cum = defaultdict(list)
    for k in items.keys():
        sum_val = 0
        for e in items[k]:
            sum_val += e
            cum[k].append(sum_val)

    max_val = 0
    weights = items.keys()
    kinds = len(items.keys())
    for element in itertools.product(range(N + 1), repeat = kinds):
        w_sum = 0
        over_flag = False
        for i in range(kinds):
            if element[i] > item_num[weights[i]]:
                over_flag = True
                break
            w_sum += weights[i] * element[i]

        if w_sum > W or over_flag:
            continue

        val = 0
        for i in range(kinds):
            if element[i] >= 1:
                val += cum[weights[i]][element[i] - 1]
        if val > max_val:
            max_val = val

    print max_val


### FIXED CODE ###

#coding:utf-8

N, W = map(int, raw_input().split(" "))
items = [tuple(map(int, raw_input().split(" "))) for _ in range(N)]
dic = {}

def search(i, j):
    if i == N:
        return 0
    if (i, j) not in dic:
        dic[(i, j)] = search(i + 1, j)
        w, v = items[i]
        if j + w <= W:
            dic[(i, j)] = max(dic[(i, j)] , search(i + 1, j + w) + v)
    return dic[(i, j)]

print search(0, 0)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()


def check(x):
    # k番目の数がx以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    for i, ai in enumerate(a):
        if ai > 0:
            idx = bisect_right(a, x // ai)
            cnt += max(idx - i - 1, 0)
        elif ai < 0:
            idx = bisect_left(a, -(x // abs(ai)))
            # cnt += n - idx
            cnt += n - max(idx, i + 1)
        else:
            # ai == 0
            if x >= 0:
                cnt += n - i - 1

        if cnt >= k:
            return True
    # print('check', x, cnt)
    return cnt >= k


# lb = -10**18  # False
# ub = +10**18  # True
lb = min(a[0]**2, a[0] * a[-1], a[-1]**2) - 1  # False
ub = max(a[0]**2, a[0] * a[-1], a[-1]**2) + 1  # True

while ub - lb > 1:
    mid = (ub + lb) // 2
    # print(lb, ub)
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

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

a_minus = a_zero = a_plus = 0
for i in range(n):
    if a[i] > 0:
        a_plus += 1
    elif a[i] == 0:
        a_zero += 1
    else:
        a_minus += 1

aa_minus = a_minus * a_plus
aa_zero = a_zero * (n - a_zero) + a_zero * (a_zero - 1) // 2


def check_minus(x):
    # k番目の数がx(<0)以下であるか
    # x以下の数字がk個以上あるか
    cnt = 0
    j = a_minus + a_zero
    for i in range(a_minus):
        # a[i] < 0
        while j < n and a[i] * a[j] > x:
            j += 1
        cnt += n - j

    return cnt >= k


def check_plus(x):
    # k番目の数がx(>0)以下であるか
    # x以下の数字がk個以上あるか

    def func(b, m):
        # 昇順ソート済みの数列b (長さm)
        # 掛け算してx以下となる数を求める
        c = 0
        j = m - 1
        for i in range(m):
            while j > 0 and b[i] * b[j] > x:
                j -= 1
            c += max(j - i, 0)
        return c

    cnt = aa_minus + aa_zero
    cnt += func(a[-a_plus:], a_plus)
    cnt += func(list(reversed(a[:a_minus])), a_minus)
    return cnt >= k


if k <= aa_minus:
    # k番目の数は負の数
    lb = a[0] * a[-1] - 1  # False
    ub = 0  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_minus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub
elif k <= aa_minus + aa_zero:
    # k番目の数は0
    ans = 0
else:
    # k番目の数はプラス
    lb = 0  # False
    ub = max(a[0]**2, a[-1]**2) + 1  # True
    while ub - lb > 1:
        mid = (ub + lb) // 2
        if check_plus(mid):
            ub = mid
        else:
            lb = mid

    ans = ub

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

import bisect
n = int(input())
k = []
for _ in range(3):
    a = [int(i) for i in input().split()]
    a.sort()
    k.append(a)
#print(k)
count = 0
for i in k[0]:
    b = bisect.bisect_right(k[1],i)
    for j in k[1][b:n]:
        #print(j)
        c = bisect.bisect_right(k[2],j)
        #print(c)
        count += n-c 
print(count)


### FIXED CODE ###

import bisect
n = int(input())
k = []
for _ in range(3):
    a = [int(i) for i in input().split()]
    a.sort()
    k.append(a)
count = 0
for i in k[1]:
    b = bisect.bisect_left(k[0],i)
    c = bisect.bisect_right(k[2],i)
    count += b*(n-c)
print(count)
### BUGGY CODE ###

S = input()
n = len(S)
t = [0]*(n+1)
d = 1
l = [0]*2019

t[n] = 0
t[n-1] = int(S[n-1])

l[0] += 1

for i in range(n-1, -1, -1):
    t[i] = int(S[i]+str(t[i+1]))
    l[t[i]%2019] += 1 

print(sum(map(lambda x: x*(x-1)//2, l)))

### FIXED CODE ###

import sys

input = sys.stdin.readline

S = input().rstrip()
n = len(S)
l = [0]*2019
d = 10

t = int(S[n-1])
l[t%2019] += 1

l[0] += 1

for i in range(n-2, -1, -1):
    t += int(S[i])*d%2019
    l[t%2019] += 1 
    d *= 10
    d %= 2019

ans = 0

for i in l:
    ans += i*(i-1)//2

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

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
d.sort()
t.sort()
D=set(d)
T=set(t)
for i in T:
  if i not in D:
    print('NO')
    exit()
  else:
    if t.count(i)>d.count(i):
      print('NO')
      exit()
print('YES')

### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
m=int(input())
t=list(map(int,input().split()))
if n<m:
  print('NO')
  exit()
d.sort()
t.sort()
i=0
j=0
while i<n and j<m:
  if d[i]==t[j]:
    i+=1
    j+=1
  else:
    i+=1
if j==m:
  print('YES')
else:
  print('NO')
### BUGGY CODE ###

import sys, collections
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]

def height(C):
    P = []
    for i in range(W):
        p = 0
        for j in range(len(C)):
            if C[j][i] == 1:
                p = 0
            else: p += 1
        P.append(p)
    return P

def square(C):
    P = height(C)
    G = []
    L = collections.deque()
    for i,v in enumerate(P):
        if not L:
            L.append((i, v))
            continue
        if v > L[-1][1]:
            L.append((i, v))
        elif v < L[-1][1]:
            k = i - 1
            while L and v < L[-1][1]:
                a = L.pop()
                G.append((k - a[0] + 1) * a[1])
            L.append((a[0], v))
    while L:
        a = L.pop()
        G.append((len(P) - a[0]) * a[1])
    return max(G)

def ans(C):
    ans = []
    for i in range(H):
        currentC = C[:i+1]
        ans.append(square(currentC))
    return str(max(ans))
print(ans(C))

### FIXED CODE ###

import sys, collections, heapq
file = sys.stdin
H,W = map(int, file.readline().split())
C = [list(map(int,i.split())) for i in file.readlines()]
prev = [0 for i in range(W)]
G = []
def height(C):
    global prev
    P = []
    for i in range(W):
        if C[-1][i] == 1:
            p = 0
        else: p = prev[i] + 1
        P.append(p)
    prev = P[:]
    return P

def square(C):
    P = height(C)
    global G
    L = collections.deque()
    for i,v in enumerate(P):
        if not L:
            L.append((i, v))
            continue
        if v > L[-1][1]:
            L.append((i, v))
        elif v < L[-1][1]:
            k = i - 1
            while L and v < L[-1][1]:
                a = L.pop()
                heapq.heappush(G,  -(k - a[0] + 1) * a[1])
            L.append((a[0], v))
    while L:
        a = L.pop()
        heapq.heappush(G, -(len(P) - a[0]) * a[1])

def ans(C):
    ans = []
    global G
    for i in range(H):
        currentC = C[:i+1]
        square(currentC)
    return str(-G[0])

print(ans(C))