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

import sys
from functools import lru_cache
sys.setrecursionlimit(10**7)
N = int(input())
@lru_cache(None)
def f(n):
  if n<10:
    if n<=5:
      return n
    else:
      return 10-n+1
  p,q = divmod(n,10)
  
  return min(f(p)+q, f(p+1)+10-q)
print(f(N))

### FIXED CODE ###

N = [int(c) for c in input()]
dp = 0,1
for i in range(len(N)):
  a = min(dp[0]+N[i], dp[1]+10-N[i])
  b = min(dp[0]+N[i]+1, dp[1]+10-N[i]-1)
  dp = a,b
print(dp[0])
### BUGGY CODE ###

n, k = input().split()
p = list(map(float, input().split()))

n, k = int(n), int(k)

ans = 0

for i in range(n - k + 1):
    c = 0
    for j in range(k):
        c += p[i + j]
    c += k
    if c >= ans:
        ans = c


print(ans / 2)

### FIXED CODE ###

N,K = map(int,input().split())
Data  = map(int,input().split())
Data2 = [0]*N
for idx,data in enumerate(Data):
    e = data * (data+1) / 2 / data
    Data2[idx] = e
#print(Data2)
sum1 = 0
for i in range(K):
    sum1 += Data2[i]
ans = sum1
for i in range(0,N-K):
    sum1 -= Data2[i]
    sum1 += Data2[i+K]
    if ans < sum1:
        ans = sum1
print(ans)
### BUGGY CODE ###

import collections as col
n = int(input())
a = list(map(int,input().split()))
cnt = col.Counter(a)

for i in range(n):
    cnt[a[i]] -= 1
    ans = 0
    for key,val in cnt.items():
        ans += val*(val-1)//2
    print(ans)
    cnt[a[i]] += 1


### FIXED CODE ###

import collections as col
n = int(input())
a = list(map(int,input().split()))
cnt = col.Counter(a)

ans = 0
for key,val in cnt.items(): ans += val*(val-1)//2

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


     

import math
import numpy as np


H,N = map(int,input().split())
Damage = []
Cost = []


DP = [0] + [pow(10,9)] * (H+1)



for i in range(N):
    a,b = map(int,input().split())
    Damage.append(a)
    Cost.append(b)
    
#print(DP)

damage = np.array(Damage)
cost = np.array(Cost)
dp = np.array(DP)




# DP[i] = best magic points to do i damage

for i in range(1,len(dp)):
    for spell in range(N):
        dp[i] = min(dp[i],dp[max(0,i-damage[spell])]+cost[spell])




print (dp[H])



### FIXED CODE ###


     

import math



H,N = map(int,input().split())
Damage = []
Cost = []


DP = [0] + [pow(10,9)] * (H+1)



for i in range(N):
    a,b = map(int,input().split())
    Damage.append(a)
    Cost.append(b)
    
#print(DP)


# DP[i] = min magic points to do i damage

for i in range(1,len(DP)):
    for spell in range(N):
        DP[i] = min(DP[i],DP[max(0,i-Damage[spell])]+Cost[spell])




print (DP[H])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
p = []
ans = 0
for _ in range(N):
    x,y = map(int,input().split())
    p.append((x,y))

for i in range(N):
    xi,yi = p[i]
    for j in range(i+1,N):
        xj,yj = p[j]
        tmp = abs(xi-xj)+abs(yi-yj)
        ans = max(ans,tmp)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

# coding: utf-8


def det(p, q):
    return p[0]*q[1] - p[1]*q[0]


def sub(p, q):
    return (p[0]-q[0], p[1]-q[1])


def get_convex_hull(points):
    # どの3点も直線上に並んでいないと仮定する。
    n = len(points)
    points.sort()
    size_convex_hull = 0
    ch = []
    for i in range(n):
        while size_convex_hull > 1:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    t = size_convex_hull
    for i in range(n-2, -1, -1):
        while size_convex_hull > t:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    return ch[:-1]

N = int(input())
p = []
ans = 0
for _ in range(N):
    x,y = map(int,input().split())
    p.append((x,y))
if N == 2:
    x0,y0 = p[0]
    x1,y1 = p[1]
    print(abs(x0-x1)+abs(y0-y1))
    exit()

p = get_convex_hull(p)
n = len(p)
for i in range(n):
    xi,yi = p[i]
    for j in range(i+1,n):
        xj,yj = p[j]
        tmp = abs(xi-xj)+abs(yi-yj)
        ans = max(tmp,ans)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
S = [0]*N
for i in range(N):
    x, h = map(int, input().split())
    S[i] = [x, -(-h//A)]

S.sort()
print()
cnt = 0

for i in range(N):
    if S[i][1] <= 0:
        continue
    cnt += S[i][1]
    dmg = S[i][1]
    max_X = S[i][0] + D*2
    for j in range(i+1, N):
        if S[j][0] > max_X:
            break
        S[j][1] -= dmg

print(cnt)


### FIXED CODE ###

from collections import deque
import math

import sys
input = sys.stdin.readline

N, D, A = map(int, input().split())
S = [0]*N
atack = deque()
for i in range(N):
    x, h = map(int, input().split())
    S[i] = [x, h]

S.sort()
cnt = 0
dmg = 0
for i in range(N):
    while atack:
        if atack[0][0] < S[i][0]:
            x, d = atack.popleft()
            dmg -= d
        else:
            break

    if S[i][1] <= dmg:
        continue
    bomb = math.ceil((S[i][1]-dmg)/A)
    atack.append([S[i][0]+2*D, A*bomb])
    cnt += bomb
    dmg += A*bomb

print(cnt)
### BUGGY CODE ###

import sys
def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def s(): return(input())

def main():
  S = s()
  cur = [[1,S[0],""],[0,"",S[0]]]
  nxt = []
  N = len(S)
  
  for i in range(1,N):
    for c,p,n in cur:
      if len(n)==2 and p!=n+S[i]:
        nxt.append([c+1,n+S[i],""])
      elif len(n)<=1:
        nxt.append([c,p,n+S[i]])
        if p!=n+S[i]:
          nxt.append([c+1,n+S[i],""])
    nxt.sort(key = lambda x: x[0], reverse = True)
    nxt.sort(key = lambda x:(x[1],x[2]))
    cur = [nxt[0]]
    for j in range(1,len(nxt)):
      if cur[-1][1:] != nxt[j][1:]:
        cur.append(nxt[j])
    nxt = []
  r = -1
  for c,p,n in cur:
    if n == "":
      r = max(r,c)
  return r

if __name__ == "__main__":
  print(main())

      


### FIXED CODE ###

import sys
def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def s(): return(input())

def main():
  S = s()
  cur = [[1,S[0],""],[0,"",S[0]]]
  nxt = []
  N = len(S)
  
  for i in range(1,N):
    for c,p,n in cur:
      if len(n)==1 and p!=n+S[i]:
        nxt.append([c+1,n+S[i],""])
      elif len(n)==0:
        nxt.append([c,p,n+S[i]])
        if p!=n+S[i]:
          nxt.append([c+1,n+S[i],""])
    nxt.sort(key = lambda x: x[0], reverse = True)
    nxt.sort(key = lambda x:(x[1],x[2]))
    cur = [nxt[0]]
    for j in range(1,len(nxt)):
      if cur[-1][1:] != nxt[j][1:]:
        cur.append(nxt[j])
    nxt = []
  r = -1
  for c,p,n in cur:
    if n == "":
      r = max(r,c)
  return r

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

N = int(input())
a = list(map(int,input().split()))
a = sorted(a)
sai = max(a)
ans = 0
def comb(b,c):
      d = 1
      kake = b
      while d < c:
           kake = kake * (b-d)
           d += 1
           kake = kake / d
      return kake
for i in range(N):
    ro = comb(sai,a[i])
    if ro > ans:
       ans = ro
       kore = a[i]
print(sai,kore)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
a = sorted(a)
sai = max(a)
ma = 100000000000000000000000000
naka = sai / 2
for i in range(N):
    sa = abs(naka - a[i])
    if ma > sa:
       ma = sa
       kore = a[i]
print(sai,kore)
### BUGGY CODE ###

import numpy as np
N,a,b = np.array(input().split()).astype(int)
mod = 10**9+7
import math
def power(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x%mod
        x = x*x%mod
        n = n >> 1 #ビットシフト
    return ans
def fact(m, n):
    val = 1
    for i in range(m, n + 1):
        val = (val*i)%mod
    return val
def cmb(N, r):
    A = fact(N-r+1, N)
    B = math.factorial(r)
    A = (A*power(B, mod-2))%mod
    return A
print((power(2, N)-1-cmb(N, a)-cmb(N, b))%mod)

### FIXED CODE ###

import numpy as np
N,a,b = np.array(input().split()).astype(int)
mod = 10**9+7
def power(x, n):
    ans = 1
    while(n > 0):
        if(bin(n & 1) == bin(1)):
            ans = ans*x%mod
        x = (x*x)%mod
        n = n >> 1 #ビットシフト
    return ans
def fact(m, n):
    val = 1
    for i in range(m, n+1):
        val = val*i % mod
    return val
    
def cmb1(N, r):
    A = fact(N-r+1, N)%mod
    B = fact(1, r)%mod
    return A, B, (A*power(B, mod-2))%mod
def cmb2(a, b, A, B):
    A = fact(N-a+1, N-b)*A%mod
    B = fact(b+1, a)*B%mod
    return (A*power(B, mod-2))%mod
if(a>N//2):
    a = N-a
if(b>N//2):
    b = N-b
tmp = max(a,b)
b = min(a,b)
a = tmp
A, B, K1 = cmb1(N, b)
K2 = cmb2(a, b, A, B)
print((power(2, N)-1-K1-K2)%mod)
### BUGGY CODE ###

a = int(input())
b= [int(x) for x in input().split()]
c = a
for s in range(a):
  d = b[s]
  e = b[s]
  for t in b[s+1::]:
    d = d ^ t
    e = e + t
    if d == e:
      c += 1
    else:
      break
print(c)

### FIXED CODE ###

N = int(input())
A= [int(x) for x in input().split()]
A.append(0)
count = N
s = 0
t = 1
xor = A[0]
while s < N - 1:
  while t < N:
    if not A[t] or not (xor & A[t]):
      xor ^= A[t]
      t += 1
    else:
      break
  count += t - s - 1
  while s < t:
    xor ^= A[s]
    s += 1
    if xor & A[t]:
      count += t - s - 1
      continue
    else:
      break
  if s == t:
    xor = A[s]
    t += 1
print(count)
### BUGGY CODE ###

import functools
import operator

N = int(input())
power_list = [x+1 for x in range(N)]
result = functools.reduce(operator.mul, power_list)
print(result % (10**9+7))

### FIXED CODE ###

N = int(input())
 
power = 1
for i in range(1,N+1):
    power *= i
    if power >= 10**9+7:
        power %= 10**9+7
print(power % (10**9+7))
### BUGGY CODE ###

def solve(n):
	A=[0 for i in range(n+1)]
	for i in range(2,n+1):
		cnt=0
		for j in range(1,i+1):
			if i%j==0:
				cnt+=1
		if cnt==2:#1??¨????????°??????
			A[i]=1
	cnt=0
	for i in A:
		if i==1:
			cnt+=1
	return cnt 

while True:
	try:
		n = int(input())
		print(solve(n))
	except EOFError:
		break

### FIXED CODE ###

def sieve(n):
	p=[True for i in range(n+1)]
	p[0]=p[1]=False
	for i in range(2,n+1):
		if p[i]==True:
			for j in range(i*i,n+1,i):
				p[j]=False
	return p

def solve(n):
		if n<2:return 0
		c=1
		for i in range(3,n+1,2):
			if p[i]==1:
				c+=1
		return c

p=sieve(1000000)
while True:
	try:
		n = int(input())
		print(solve(n))
	except EOFError:
		break
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
import math
mod = 10**9 + 7
def I(): return int(input())
def II(): return map(int, input().split())
def L(): return list(map(int, input().split()))
def TWO(M):
  L=[0]*M
  R=[0]*M
  for i in range(M):
    L[i],R[i] = II()
  return L, R

N = I()
A = [0]*N
for i in range(N):
  A[i] = I()

check = [0]*N
counter = 0
all_counter = 0
not_used1 = [i for i in range(N)]
not_used2 = [i for i in range(N)]
while 1:
  temp = -1
  for i in not_used1:
    if temp<A[i]:
      temp = A[i]
      all_counter += 1
      not_used2.remove(i)
  not_used1 = not_used2[:]
  counter += 1
  if all_counter==N:
    break
  
print(counter)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_left

N = I()
A = [0]*N
for i in range(N):
    A[i] = I()

val = [-1]*N
for i in range(N):
    temp = bisect_left(val,A[i])
    val[temp-1] = A[i]

ans = 0
for i in range(N):
    if val[i]!=-1:
        ans += 1

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

import numpy as np
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=np.zeros(n+1,np.int64)
# dp[i]:足場iに到達するための最小コスト。はじめカエルは足場1にいるのでdp[1]=0
dp[1]=0
dp[2]=abs(h[0]-h[1])
for i in range(3,n+1):      
      dp[i]=np.min([dp[i-j]+abs(h[i-1]-h[i-j-1]) for j in range(1,min(k+1,i))])
print(dp[n])

### FIXED CODE ###

n,k=map(int,input().split())
import numpy as np
h=np.array(input().split(),np.int64)
if n<3:
  print(abs(h[0]-h[1]))
  exit()
dp=np.zeros(n)
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
  j=max(0,i-k)
  dp[i]=np.min(dp[j:i]+np.abs(h[i]-h[j:i]))
  #dp[i]=min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(k+1,i+1))])
print(int(dp[-1]))
### BUGGY CODE ###

import math
MOD = 10**9 + 7
def cc(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = format(a[i], '060b')
s = 0
for i in range(60):
    c0 = 0
    c1 = 0
    for j in range(n):
        if a[j][i] == '0':
            c0 += 1
        else:
            c1 += 1
    s += pow(2,59-i,MOD)*c0*c1
    s %= MOD
print(s)

### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = 0
m = 1
for i in range(60):
    c = sum(ai & m for ai in a)
    c //= m
    s = (s + m*c*(n-c))%MOD
    m <<= 1
print(s)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

n, m, p = map(int, input().split())
edge = []
edge_inv = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a, b, -c+p))
    edge_inv[b].append(a)


visited = [False] * n
def dfs(v):
    for u in edge_inv[v]:
        if not visited[u]:
            visited[u] = True
            dfs(u)

visited[n-1] = True
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    update = False
    for v_from, v_to, cost in edge:
        if v_from not in target_nodes or v_to not in target_nodes:
            continue
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            update = True
            d[v_to] = d[v_from] + cost


if update:
    print(-1)
else:
    print(max(0, -d[n-1]))


### FIXED CODE ###

n, m, p = map(int, input().split())
graph = [[] for _ in range(n)]
edge = []
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, -c+p))
    edge.append((a, b, -c+p))

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost

exist = True
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost
            if v_to == n - 1:
                exist = False

if not exist:
    print(-1)
else:
    print(max(0, -d[n-1]))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
k,q=map(int,input().split())
D=[int(i) for i in input().split()]
for _ in range(q):
  n,x,m=map(int,input().split())
  DD=[d%m for d in D]
  x%=m
  ans=n-1
  u,v=(n-1)//k,(n-1)%k
  z1,z2,r,s=0,0,0,0
  for i,d in enumerate(DD):
    s+=d
    if i<v:
      r+=d
      if d==0:
        z1+=1
        z2+=1
    elif d==0:
      z2+=1
  ans-=(z2*u+z1)+(x+s*u+r)//m
  print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
k,q=map(int,input().split())
D=[int(i) for i in input().split()]
for _ in range(q):
  n,x,m=map(int,input().split())
  DD=[d%m for d in D]
  x%=m
  ans=n-1
  u,v=(n-1)//k,(n-1)%k
  z1,z2,r,s=0,0,0,0
  for i,d in enumerate(DD):
    s+=d
    if i<v:
      r+=d
      if d==0:
        z1+=1
        z2+=1
    elif d==0:
      z2+=1
  ans-=(z2*u+z1)+(x+s*u+r)//m
  print(ans)
### BUGGY CODE ###

import queue

h, w = map(int, input().split())
s = '#'*(w+2)
for _ in range(h):
    s += '#' + input() + '#'
s += '#'*(w+2)

def bfs():
    step = [0]*(w+2)*(h+2)
    step[w+2+1] = 1
    q = queue.Queue()
    q.put(w+3)
    while q:
        x = q.get()
        for i in (1, -1, w+2, -w-2):
            if s[x+i] == '#':
                continue
            if x+i == (w+2)*(h+1) - 2:
                step[x+i] = step[x] + 1
                return step[x+i]
            if step[x+i] == 0:
                step[x+i] = step[x] + 1
                q.put(x+i)
    print(-1)
    exit()

count = 0
for j in range((w+2)*(h+2)):
    if s[j] == '.':
        count += 1

print(count - bfs())

### FIXED CODE ###

import queue

h, w = map(int, input().split())
s = '#'*(w+2)
for _ in range(h):
    s += '#' + input() + '#'
s += '#'*(w+2)

def bfs():
    step = [0]*(w+2)*(h+2)
    step[w+2+1] = 1
    q = queue.Queue()
    q.put(w+3)
    while not q.empty():
        x = q.get()
        for i in (1, -1, w+2, -w-2):
            if s[x+i] == '#':
                continue
            if x+i == (w+2)*(h+1) - 2:
                step[x+i] = step[x] + 1
                return step[x+i]
            if step[x+i] == 0:
                step[x+i] = step[x] + 1
                q.put(x+i)
    print(-1)
    exit()

count = 0
for j in range((w+2)*(h+2)):
    if s[j] == '.':
        count += 1

print(count - bfs())
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0]*n
for i in range(n):
    ans[i]=a.index(i+1)+1
print(*ans,sep=' ')


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0]*n
b = 0
for i in a:
    ans[i-1]=b+1
    b += 1
print(*ans,sep=' ')
### BUGGY CODE ###

def main():
	n, m = list(map(int, input().split()))
	rqs = [list(map(int, input().split())) for _ in range(m)]

	rqs.sort(key = lambda x: x[1])

	cnt = 0
	while len(rqs) > 1:
		rqs = [x for x in rqs[1:] if x[0] >= rqs[0][1]]
		cnt += 1
		#print(rqs, cnt)

	if len(rqs) == 1:
		cnt += 1

	print(cnt)

if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	n, m = list(map(int, input().split()))
	rqs = [list(map(int, input().split())) for _ in range(m)]

	rqs.sort(key = lambda x: x[1])

	b = -1
	cnt = 0
	
	for x in rqs:
		if b < x[0]:
			b = x[1] - 1
			cnt += 1

	print(cnt)

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

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

ps = list(map(lambda n: (n+1)/2, ps))

mx = 0
for i in range(n - (k-1)):
  sm = sum(ps[i:i+k])
  if sm > mx:
    mx = sm
print(mx)

### FIXED CODE ###

n, k = map(int, input().split())
ps = list(map(lambda n: (int(n)+1)/2, input().split()))

mx = sum(ps[:k])
sm = sum(ps[:k])
for i in range(k, n):
  sm += ps[i] - ps[i-k]
  if sm > mx:
    mx = sm
print(mx)
### BUGGY CODE ###

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

# DPテーブル
dp = [10 ** 10] * N

# 初期値
dp[0] = 0

# ループ
for i in range(1, N):
    for j in range(1, K + 1):
        if i - j < 0:
            pass
        else:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

# 解を出力
print(dp[N - 1]) 


### FIXED CODE ###

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

# DPテーブル
dp = [10 ** 10] * N

# 初期値
dp[0] = 0

# ループ
for i in range(1, N):
    for j in range(1, K + 1):
        if i - j < 0:
            pass
        else:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

# 解を出力
print(dp[N - 1])
### BUGGY CODE ###

n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
for i in range(m):
    b,c=map(int,input().split())
    for k in range(b):
        if a[k]<c:
            a[k]=c
    a.sort()
print(sum(a))


### FIXED CODE ###

n,m=map(int,input().split())
a=sorted([int(i) for i in input().split()])
bc=[list(map(int,input().split())) for _ in range(m)]
bc=sorted(bc,key=lambda x : x[1],reverse=True)
min_a=min(a)
count=0
for b,c in bc:
    if min_a >=c and count>=n:
        break
    else:
        l=min(b,n-count)
        for i in range(l):
            count+=1
            a.append(c)
a.sort()
print(sum(a[count:]))
### BUGGY CODE ###

S = str(input())
s = len(S)
cnt = 0
A = [0]*2019
for i in range(s):
  x = int(S[i:])%2019
  A[x] += 1
for i in range(1,2019):
  cnt += A[i]*(A[i]-1)//2
cnt += A[0]*(A[0]+1)//2
print(cnt)

### FIXED CODE ###

S = str(input())
s = len(S)
cnt = 0
A = [0]*2019
r = 0
for i in range(s):
  x = (r+pow(10, i, 2019)*int(S[s-i-1]))%2019
  A[x] += 1
  r = x
  
for i in range(1,2019):
  if A[i] >= 2:
    cnt += A[i]*(A[i]-1)//2
cnt += A[0]*(A[0]+1)//2

print(cnt)
### BUGGY CODE ###

n, k = map(int, input().split())
hl = [int(input()) for _ in range(n)]

hl_s = sorted(hl, reverse=True)
delta = 10*10**9

if n > 1000:
    while n < 1000:
        if hl_s[n//2] < (hl_s[0] + hl_s[n-1])//2:
            hl_s = hl_s[:n//2]
        else:
            hl_s = hl_s[n//2:]
        n = len(hl_s)

for i in range(len(hl_s)-k+1):
    h_max = max(hl_s[i:i+k])
    h_min = min(hl_s[i:i+k])
    if delta > (h_max - h_min):
        delta = h_max - h_min
    if delta == 0:
        break

print(delta)

### FIXED CODE ###

n, k = map(int, input().split())
hl = [int(input()) for _ in range(n)]
hl.sort()

h_min = min(hl[i+k-1] - hl[i] for i in range(n-k+1))
print(h_min)
### BUGGY CODE ###

n,m = map(int,input().split())
alist = list(map(int,input().split()))
for i in range(m):
  alist[alist.index(max(alist))] //= 2
print(sum(alist))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from math import log

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

table = [[0]*(int(log(a[-1],2))+2) for i in range(n)]

for i in range(n):
    for y in range(int(log(a[-1],2))+2):
        table[i][y] = a[i]//pow(2,y)
        if a[i]//pow(2,y) == 0:
            break

s_table = [[0]*(int(log(a[-1],2))+2) for i in range(n)]
for i in range(n):
    s_table[i][0] = table[i][0]

import heapq
hq = []
heapq.heapify(hq)
h_push = heapq.heappush
h_pop = heapq.heappop

for i in range(n):
    for y in range(1,int(log(a[-1],2))+2):
        s_table[i][y] = table[i][y]-table[i][y-1]
        h_push(hq,table[i][y]-table[i][y-1])
        if table[i][y]-table[i][y-1] == -1:
            break


ans = sum(a)

for i in range(m):
    if not hq:
        print(0)
        exit()
    ans += h_pop(hq)
    
print(ans)
### BUGGY CODE ###

R, G, B, N= map(int, input().split())
c = 0
for i in range(N//R + 1):
  for j in range(N//G + 1):
    for k in range(N//B + 1):
      if R * i + G * j + B * k == N:
        c += 1
print(c)

### FIXED CODE ###

R, G, B, N= map(int, input().split())
c = 0
S = [R, G, B]
S.sort()
R = S[2]
G = S[1]
B = S[0]

if S[0] == 1:
  for i in range(N//R + 1):
    for j in range(N//G + 1):
      if R * i + G * j <= N:
        c += 1
else:
  for i in range(N//R + 1):
    for j in range(N//G + 1):
      for k in range(N//B + 1):
        if R * i + G * j + B * k == N:
          c += 1
print(c)