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

S = input()
digits = list(map(int, S))
divisor = 2019

rem_count = [0] * divisor
rem_count[0] = 1
num = 0
pow10 = 1
total = 0

for digit in reversed(digits):
    num = digit * pow10 + num
    total += rem_count[num % divisor]
    pow10 *= 10
    rem_count[num % divisor] += 1

print(total)


### FIXED CODE ###

S = input()
digits = list(map(int, S))
divisor = 2019

rem_count = [0] * divisor
rem_count[0] = 1
num = 0
pow10 = 1
total = 0

for digit in reversed(digits):
    num = digit * pow10 + num
    num %= divisor
    total += rem_count[num % divisor]
    pow10 *= 10
    pow10 %= divisor
    rem_count[num % divisor] += 1

print(total)
### BUGGY CODE ###

H, W, M = [int(x) for x in input().split()]

width = [0] * W
height = [0] * H

obj = set()
for i in range(M):
    h, w = [int(x) - 1 for x in input().split()]

    width[w] += 1
    height[h] += 1
    obj.add((h, w))

for idx_h, h in [(idx_h, h) for idx_h, h in enumerate(height) if h == max(height)]:
    for idx_w, w in [(idx_w, w) for idx_w, w in enumerate(width) if w == max(width)]:
        if not (idx_h, idx_w) in obj:
            print(h + w)
            exit()

print(max(height) + max(width) - 1)


### FIXED CODE ###

import numpy
H, W, M = [int(x) for x in input().split()]

width = numpy.array([0] * W, dtype='int64')
height = numpy.array([0] * H, dtype='int64')

obj = set()
for i in range(M):
    h, w = [int(x) - 1 for x in input().split()]

    width[w] += 1
    height[h] += 1
    obj.add((h, w))

result_h = set(numpy.where(height == numpy.max(height))[0])
result_w = set(numpy.where(width == numpy.max(width))[0])

if len(result_h) * len(result_w) > M:
    print(numpy.max(height) + numpy.max(width))
    exit()

for h in result_h:
    for w in result_w:
        if not (h, w) in obj:
            print(numpy.max(height) + numpy.max(width))
            exit()

print(numpy.max(height) + numpy.max(width) - 1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n,k = map(int, input().split())

################
p = 10**9 + 7
def comb(n,k,p):
  ans = 1
  for i in range(1,k+1):
    ans = ans * (n - (i-1)) % p
    ans = ans * pow(i, p-2, p)
  return ans
################

MAX = comb(2*n-1, n, p)%p



if k >= n:
  print(MAX)
else:
  ans = 0
  for i in range(0,k+1):
    temp = comb(n-1, n-i-1, p)%p
    temp2 = comb(n, i, p)%p
    temp = temp * temp2 %p
    ans = (ans + temp ) %p
    
  print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-

MOD = 10**9 +7

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret *= kaijo(n)
  ret %= MOD;
  ret *= gyaku_kaijo(r)
  ret %= MOD;
  ret *= gyaku_kaijo(n-r)
  ret %= MOD;
  return ret




 
n,k = map(int, input().split())
 
################
#p = 10**9 + 7
#def comb(n,k,p):
#  ans = 1
#  for i in range(1,k+1):
#    ans = ans * (n - (i-1)) % p
#    ans = ans * pow(i, p-2, p)
#  return ans
################
 
if k >= n:
  ans = nCr(2*n-1, n) % MOD
else:
  ans = 0
  for i in range(0,k+1):
    temp = (nCr(n-1, i) % MOD) * (nCr(n, i) % MOD) % MOD
    ans = (ans + temp) % MOD
    
print(ans)
### BUGGY CODE ###

import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(157):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 157
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 157
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def possible():
    print("POSSIBLE")
    sys.exit()

def main():
    N, M = map(int, input().split())
    hashdict = dict()
    for i in range(1009):
        hashdict[i] = list()
    alist = list()
    for i in range(M):
        a, b = map(int, input().split())
        if a == 1:
            temp = b % 1009
            hashdict[temp].append(b)
        if b == N:
            alist.append(a)

    for start in alist:
        temp = start % 1009
        if start in hashdict[temp]:
            possible()
    print("IMPOSSIBLE")

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

import heapq
N, K = map(int,input().split())
Q = []
for i in range(N):
    a, b = map(int,input().split())
    for j in range(b):
        heapq.heappush(Q,a)
for i in range(K-1):
    heapq.heappop(Q)
print(heapq.heappop(Q))

### FIXED CODE ###

N, K = map(int,input().split())
Q = [0 for i in range(N)]
for i in range(N):
    Q[i] = list(map(int,input().split()))
Q.sort()
cnt = 0
j = 0
while cnt < K:
    cnt += Q[j][1]
    j += 1
print(Q[j-1][0])
### BUGGY CODE ###

from math import factorial
import sys

input=sys.stdin.readline

num=int(input())
#stl =[''.join(sorted(input())) for i in range(num)]
stl =[input() for i in range(num)]
stl =[''.join(sorted(i)) for i in stl]

duplicate=[x for x in set(stl) if stl.count(x) > 1]

count=0

for dup in duplicate:
    n=stl.count(dup)
    count += factorial(n) // 2 // factorial(n - 2)
print(count)

### FIXED CODE ###

num=int(input())
stl =[''.join(sorted(input())) for i in range(num)]

#duplicate=[x for x in set(stl) if stl.count(x) > 1]

t = {}
for i in range(num):
  if stl[i] in t:
    t[stl[i]] += 1
  else:
    t[stl[i]] = 1
print(sum(t[k] * (t[k] -1) // 2 for k in t))
### BUGGY CODE ###

import itertools
n, m, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

sa = list(itertools.accumulate(a))
sb = list(itertools.accumulate(b))

max = 0

for i in range(n + 1):
    for j in range(m + 1):
        if (sa[i] + sb[j] <= k):
            if i + j > max:
                max = i + j 
        else:
            break
print(max)

### FIXED CODE ###

import itertools
n, m, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [0] + list(map(int, input().split()))

sa = list(itertools.accumulate(a))
sb = list(itertools.accumulate(b))

output = 0
j = m
for i in range(n + 1):
    if sa[i] > k:
        break
    while sa[i] + sb[j] > k:
        j -= 1
    if output < i + j:
        output = i + j
print(output)
### BUGGY CODE ###

S = input()
Q = int(input())

for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        S = S[::-1]
    else:
        S = q[2] + S if q[1]=='1' else S + q[2]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
line = True
first, last = '',''

for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        line = True if line==False else False
    else:
        if line == True:
            if q[1] == '1':
                first = q[2] + first
            else:
                last = last + q[2]
        elif line==False:
            if q[1] == '1':
                last = last + q[2]
            else:
                first = q[2] + first
S = first+S+last
print(S if line else S[::-1])
### BUGGY CODE ###

import sys
si = sys.stdin.readline

d = ['R', 'G', 'B']


def main():
    n = int(si())
    l = list(si())
    dc = d[:]
    count = 0
    for i in range(n):
        r1 = l[i]
        dc.remove(r1)
        for j in range(i+1, n):
            if l[j] in dc:
                r2 = l[j]
                dc.remove(r2)
                for k in range(j+1, n):
                    if l[k] in dc:
                        count += 1
                if (j+j-i) < n and l[j+j-i] in dc:
                    count -= 1
                dc += [r2]
        dc += [r1]
    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
si = sys.stdin.readline
so = sys.stdout.write


def main():
    n = int(si())
    s = si()[:-1]
    cnt = s.count('R')*s.count('G')*s.count('B')

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

    print(cnt)


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

# -*- coding: utf-8 -*-
import sys

def main():
	N, W = map(int, input().split(" "))
	objs = []
	for _ in range(N):
		w, v = map(int, input().split(" "))
		objs.append((w, v))
		
	DP = [[0 for _ in range(W+2)] for _ in range(N+1)]
	
	for i, val in enumerate(objs):
		w, v = val
		for j in range(1, W+1):
			DP[i+1][j] = max(DP[i+1][j], DP[i][j])
			if j - w >= 0:
				#print("{} {}".format(j+w, i+1))
				DP[i+1][j] = max(DP[i+1][j], DP[i][j-w] + v)
				
	print(DP[N][W])
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def main():
	N, W = map(int, input().split())
	wv = []
	for i in range(N):
		w, v = map(int, input().split())
		if w <= W:
			wv.append((w,v))
		
	DP = [[0 for _ in range(100001)] for _ in range(N)]
	
	for i, val in enumerate(wv):
		w, v = val
		if i == 0:
			DP[i][w] = v
			continue
			
		for j in range(W):
			DP[i][j] = max(DP[i-1][j], DP[i][j])
			
			if j+w <= W:
				DP[i][j+w] = max(DP[i-1][j] + v, DP[i][j+w])
			
	print(max(DP[N-1]))
	
if __name__ == "__main__":
	main()
### BUGGY CODE ###

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

l = []
A = 0
B = 0
ans = 1
if M > 0:
    A, B = map(int, input().split())
    l.append((A, B))
for i in range(M-1):
    A, B = map(int, input().split())
    hit = None
    for tup in l:
        if A in tup or B in tup:
            if hit != None:
                hit = tuple(set(hit+tup+(A, B)))
            else:
                hit = tuple(set(tup+(A, B)))
            l.remove(tup)
    if hit != None:
        l.append(hit)
    else:
        l.append((A, B))

if len(l) > 0:
    ans = 1
for item in (l):
    if ans < len(item):
        ans = len(item)
print(ans)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())
uf = UnionFind(N)

ans = 0
for i in range(M):
    A, B = map(int, input().split())
    uf.union(A-1, B-1)

for i in range(uf.group_count()):
    if ans < uf.size(i):
        ans = uf.size(i)
print(ans)
### BUGGY CODE ###

N = int(input())
import numpy as np
#max=int(np.sqrt(N))

for n in range(1,N+1):
    j=0
    min = 1
    max = int(np.sqrt(abs(n-2)))
    #print(max)
    for x in range(min,max):
        #print(f'max:{max}')
        for y in range(min, max):
            for z in range(min, max):
                if x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x > n:
                    break
                if x**2+y**2+z**2+x*y+y*z+z*x==n:
                    if j==0:
                        max = z+1
                        min = x
                        #print(x, y, z)
                        #print(f'n:{n}')
                        j += 1
                    else:
                        j += 1
    print(j)


### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
	for j in range(1,105):
		for k in range(1,105):
			v = i*i+j*j+k*k+i*j+j*k+k*i;
			if v<10050:
				ans[v]+=1

for i in range(n):
  	print(ans[i+1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
def gcm(a, b):
  if a < b:
    a = a+b
    b=a-b
    a = a-b
  if b == 0:
    return a
  else:
    r = a%b
    return b if r == 0 else gcm(b, r)
ans = 0
for i in range(N):
  g = 0
  for j in range(i):
    g = gcm(g, A[j])
  for j in range(i+1,N):
    g = gcm(g, A[j])
  ans = max(g, ans)
print(ans)



### FIXED CODE ###

from collections import deque
def gcm(a, b):
  if a < b:
    a = a+b
    b=a-b
    a = a-b
  if b == 0:
    return a
  else:
    r = a%b
    return b if r == 0 else gcm(b, r)
N = int(input())
A = list(map(int, input().split()))
L = deque([0])
for i in range(1, N):
  L.append(gcm(L[-1],A[i-1]))
R = deque([0])
for i in reversed(range(N-1)):
  R.appendleft(gcm(R[0],A[i+1]))
ans = 0
for i in range(N):
  ans = max(ans, gcm(L[i],R[i]))
print(ans)
### BUGGY CODE ###

# @oj:atcoder
# @id: hitwanyang
# @email: 296866643@qq.com
# @date: 2020-04-20 10:31
# @url:https://atcoder.jp/contests/dp/tasks/dp_b
import sys
def input():
    return sys.stdin.readline().strip()

def main():
    nk=list(map(int,input().split()))
    h=list(map(int,input().split()))
    n=nk[0]
    k=nk[1]
    dp=[10**9]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        for j in range(i-k,i):
            if j>=0:
                dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i])

    print (dp[-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    size, jumps = map(int, input().split())
    array = list(map(int, input().split()))
    dp = [999999999] * size
    dp[0]= 0
    dp[1] = abs(array[0]- array[1])
    for i in range(2,size):
        dp[i] = min(abs(array[i] - array[j]) + dp[j] for j in range(max(0, i - jumps), i))
    print(dp[size-1])

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

import itertools

n, k = map(int, input().split())
lst = [int(i) for i in input().split()]

lists = list(itertools.combinations(range(n), k))
#print(lists)
min_price = float('inf')
for each in lists:
  total = 0
  for index in each:
    total += lst[index]
  if total < min_price:
    min_price = total
print(min_price)

### FIXED CODE ###

n, k = map(int, input().split())
lst = [int(i) for i in input().split()]

count = 0
min_price = 0
while count < k:
  #print(count)
  total = min_price
  for i in range(len(lst)):
    total += lst[i]
    #print(total)
    if i == 0:
      min_price = total
      min_index = i
    elif total < min_price:
      min_price = total
      min_index = i
    total -= lst[i]
  lst.pop(min_index)
  count += 1
print(min_price)
### BUGGY CODE ###

N, M = map(int, input().split())
ms = []
#m_id = []
for i in range(M):
    pi, mi = map(int, input().split())
    ms.append([pi, mi, i])
    #m_id.append(i)
    
ms = sorted(sorted(ms, key=lambda x: x[1]), key=lambda y: y[0])
#m_id = sorted(sorted(m_id, key=lambda x: ms[x][1]), key=lambda y: ms[y][0])

ans_list = []
cnt = 0
for j in range(M):
    if j == 0 or ms[j][0] == ms[j - 1][0]:
        cnt += 1
    else:
        cnt = 1
    num = str(ms[j][0]).zfill(6) + str(cnt).zfill(6)
    ans_list.append(num)
    
id_order = [i[2] for i in ms]
ans_list = sorted(ans_list, key=lambda z: id_order[ans_list.index(z)])

for ans in ans_list:
    print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = [''] * M
P = [[] for _ in range(N)]
for i in range(M):
    pi, yi = map(int, input().split())
    P[pi-1].append((yi, i))

for j, pref in enumerate(P):
    pref = sorted(pref, key=lambda x: x[0])
    for k, (yi, i) in enumerate(pref):
        A[i] += str(j+1).zfill(6) + str(k+1).zfill(6)
        
for a in A:
    print(a)
### BUGGY CODE ###

x,y = map(int,input().split())
li = list(map(int,input().split()))
li.sort()
score = 0
for i in range(y):
  li[li.index(max(li))] //= 2
for j in li:
  score += j
print(score)

### FIXED CODE ###

import heapq

n, m = map(int,input().split())
li = list(map(lambda x: int(x)*(-1),input().split()))

heapq.heapify(li)

for i in range(m):
    a = heapq.heappop(li)
    a = (-a) // 2
    heapq.heappush(li,-a)

print(-sum(li))
### BUGGY CODE ###

n = int(input())

li = []

for i in range(n):
    li.append(int(input()))

check_li = [1]
s = 1
cnt = 0

while True:
    cnt += 1
    s = li[s-1]
    if s in check_li:
        print(-1)
        break
    if s == 2:
        print(cnt)
        break
    check_li.append(s)
    
    

### FIXED CODE ###

n = int(input())

li = [int(input()) for _ in range(n)]

check_li = [1]
s = 1
cnt = 0

while True:
    cnt += 1
    s = li[s-1]
    if cnt >= n:
        print(-1)
        break
    if s == 2:
        print(cnt)
        break
### BUGGY CODE ###

n,m = map(int, input().split())

a = [int(i) for i in input().split()]

l = [0,2,5,5,4,5,6,3,7,6]
inf = float("INF")
dp = [-inf] * (n+10)
dp[0] = 0
for i in range(n):
  if dp[i] == -inf: continue
  tmp = dp[i]
  k = 1
  while tmp:
    tmp //= 10
    k *= 10
  for ai in a:
    dp[l[ai] + i] = max(dp[l[ai] + i], dp[i] + k * ai, dp[i] * 10 + ai)
print(dp[n])


### FIXED CODE ###

#A
"""
a,b = map(int, input().split())
if b % a == 0:
    print(b + a)
else:
    print(b-a)
"""

#B
"""
n, m = map(int, input().split())
ans = list(map(int, input().split()))
del ans[0]
ans = set(ans)
for i in range(n-1):
    a = list(map(int, input().split()))
    del a[0]
    ans = ans & set(a)
print(len(ans))
"""


#C
"""
import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

n = int(input())
a = list(map(int, input().split()))
print(gcd_list(a))
"""

#D
n,m = map(int, input().split())
a = list(map(int, input().split()))
num = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
ans = [-float("inf") for _ in range(n + 1)]
num_ans = []
a.sort(reverse=True)
for i in a:
    num_ans.append(num[i])
ans[0] = 0
for i in range(n + 1):
    for b in num_ans:
        if i - b >= 0:
            ans[i] = max(ans[i - b] + 1, ans[i])
anse = ""
while ans[n] > 0:
    for k, i in enumerate(num_ans):
        if n - i >= 0:
            
            if ans[n] - 1 == ans[n - i]:
                anse += str(a[k])
                n -= i
                break
    if n < 0:
        break
            
print(anse)
### BUGGY CODE ###

s=list(input())
ans=0
while s:
    a=s[0]
    b=s[-1]
    if a==b:
        s=s[1:len(s)-1]
    elif a=="x":
        s=s[1:]
        ans+=1
    elif b=="x":
        s=s[:len(s)-1]
        ans+=1
    else:
        print(-1)
        exit()

print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
s=input()[:-1]
ans=0
while s:
    a=s[0]
    b=s[-1]
    if a==b:
        s=s[1:-1]
        continue
    elif a=="x":
        s=s[1:]
        ans+=1
        continue
    elif b=="x":
        s=s[:-1]
        ans+=1
        continue
    else:
        print(-1)
        exit()

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

N = int(input())
s = ['']*N
 
for i in range(N):
  str = input()
  s[i] = ''.join(sorted(str))
 
s.sort()
ans = 0
for i in range(N):
  ans += s[i+1:].count(s[i])
  
print(ans)


### FIXED CODE ###

N = int(input())
s = ['']*N
 
for i in range(N):
	str = input()
	s[i] = ''.join(sorted(str))
 
s.sort()
ans = 0

#for i in range(N):
i = 0
while (i < N):
	current = s[i]
	same = 1
	while(i < N-1):
		if(s[i+1] == current):
			i += 1
			same += 1
		else:
			break

	ans += same * (same - 1)//2
	#print(i, same, ans)
	i += 1

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

import sys
sys.setrecursionlimit(10**6)


def dfs(v, e, visited, dp):
    if v in visited:
        return []
    ret = []
    if not e[v]:
        dp[v] = 0
    for next_v in e[v]:
        ret += dfs(next_v, e, visited, dp)
    ret.append(v)
    visited.add(v)
    return ret


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    e_ = [[] for _ in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        e_[v].append(u)
    topological_sorted = []
    visited = set()
    dp = [-1]*N
    for v in range(N):
        topological_sorted += dfs(v, e, visited, dp)
    for v in topological_sorted:
        for other_side in e_[v]:
            dp[other_side] = max(dp[v] + 1, dp[other_side])
    print(max(dp))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    e = [[] for _ in range(N)]
    input_edges = [0]*N
    for i in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        e[u].append(v)
        input_edges[v] += 1
    queue = deque()
    dp = [-1] * N
    for i, input_edge in enumerate(input_edges):
        if input_edge == 0:
            queue.appendleft(i)
            dp[i] = 0
    topological_sorted = []
    while queue:
        v = queue.pop()
        topological_sorted.append(v)
        for other_side in e[v]:
            input_edges[other_side] -= 1
            if input_edges[other_side] == 0:
                queue.appendleft(other_side)
    for v in topological_sorted:
        for other_side in e[v]:
            dp[other_side] = max(dp[v] + 1, dp[other_side])
    print(max(dp))


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

N,x =map(int,input().split())
a=list(map(int,input().split()))
cnt=0
for i in range(N-1):
    if a[i]+a[i+1]>x:
        while a[i+1]>0 and a[i]+a[i+1]>x:
            a[i+1]-=1
            cnt+=1
#端はこの操作では実現できない可能性があるので別に
if a[0]+a[1]>x:
    while a[0]+a[1]>x:
        a[0]-=1
        cnt+=1
if a[-1]+a[-2]>x:
    while a[-1]+a[-2]>x:
        a[-1]-=1
        cnt+=1
print(cnt)

### FIXED CODE ###

N,x =map(int,input().split())
a=list(map(int,input().split()))
cnt=0
for i in range(N-1):
    if a[i]+a[i+1]>x:
        #マイナスになるのを防ぐ
        if a[i+1]<(a[i]+a[i+1]-x):
            cnt+=a[i+1]
            a[i+1]=0
        else:
            cnt+=a[i]+a[i+1]-x
            a[i+1]-=a[i]+a[i+1]-x
#端はこの操作では実現できない可能性があるので別に
if a[0]+a[1]>x:
    cnt+=a[0]+a[1]-x
    a[0]-=a[0]+a[1]-x
if a[-1]+a[-2]>x:
    cnt+=a[-1]+a[-2]-x
    a[-1]-=a[-1]+a[-2]-x
print(cnt)