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

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

max = 0
for i in range(N-K+1):
  temp = 0
  for j in range(i,i+K):
    temp += l[j]
  if temp > max:
    max = temp

print((max+K)/2)

### FIXED CODE ###

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

m = 0
pre = 0
for j in range(K):
    pre += l[j]
m = pre

if K>1 and N>K:
  for i in range(N-K):
    temp = pre
    temp += l[i+K]
    temp -= l[i]
    if temp > m:
      m = temp
    pre = temp

if K==1:
  for i in range(N):
    if l[i] > m:
      m = l[i]


print((m+K)/2)
### BUGGY CODE ###

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

X = [int(x) for x in input().split()]

X.sort();

dif = [X[i+1]-X[i] for i in range(M-1)]
if M==1:
    dif = [0]
ans = sum(dif)
for i in range(N-1):
    ans -= max(dif)
    dif[dif.index(max(dif))] = 0

print(ans)


### FIXED CODE ###

import sys

N,M=[int(x) for x in input().split()]
X = [int(x) for x in input().split()]

if N>=M:
    print(0)
    sys.exit()

X.sort();

dif = [X[i+1]-X[i] for i in range(M-1)]
dif.sort()
dif.reverse()
if M==1:
    dif = [0]

ans = sum(dif)
for i in range(N-1):
    ans -= dif[i]

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

N = int(input())
A= list(map(int,input().split()))
MOD = 10**9+7
digN = 60
binA = [bin(A[i])[2:].zfill(digN) for i in range(N)]
cnt_digs = [0 for _ in range(digN)]
for i in range(N-1):
  for j in range(i+1,N):
    k = 0
    for a1,a2 in zip(binA[i], binA[j]):
      if a1 != a2:
        cnt_digs[k] += 1
      k += 1
ans = 0
mods = []
for i in range(digN):
  if i == 0:
    mods.append(2**i)
  else:
    mods.append((mods[i-1]*2)%MOD)

for i, cnt_dig in enumerate(cnt_digs):
  ii = digN - i - 1
  if cnt_dig != 0:
    ans += (mods[ii]*cnt_dig)%MOD
print(ans%MOD)

### FIXED CODE ###

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))
maxA = max(A)

maxA_len = len(bin(maxA)[2:])
num0_each_digit = [0 for _ in range(maxA_len)]
num1_each_digit = [0 for _ in range(maxA_len)]

for i in range(N):
    for i_bit, bit in enumerate(bin(A[i])[2:].zfill(maxA_len)):
        if bit == '0':
            num0_each_digit[i_bit] += 1
            num0_each_digit[i_bit] %= MOD
        else:
            num1_each_digit[i_bit] += 1
            num1_each_digit[i_bit] %= MOD
ans = 0
for i in range(maxA_len):
    factor = (2 ** (maxA_len - i - 1)) % MOD
    ans += (num0_each_digit[i] * num1_each_digit[i] * factor) % MOD

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

n = int(input())
c = input()
r=0
w=0
p=0
count = 0
for i in range(len(c)):
    if c[i]=="R":
        r+=1
    else:
        w+=1
white = []

for i in range(len(c)):
    if c[i]=="R":
        r-=1
        
    else:
        white.append(r)
    if r==0:
        break
while True:
    if len(white)==0:
        print(count)
        break
    else:
        if count>=white[0]:
            print(count)
            break
        else:
            count+=1
            white.pop(0)

### FIXED CODE ###

n = int(input())
c = input()
r=0
w=0
p=0
count = 0
for i in range(len(c)):
    if c[i]=="R":
        r+=1
    else:
        w+=1
white = []

for i in range(len(c)):
    if c[i]=="R":
        r-=1
        
    else:
        white.append(r)
    if r==0:
        break
if len(white)==0:
    print(0)
elif white[0]==0:
    print(0)
else:
    for i in range(len(white)):
        if white[-i-1]>=len(white)-i:
            print(len(white)-i)
            break
### BUGGY CODE ###

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

for i in range(n):
    b = list(a)
    del b[i]
    b.sort()
    print(b[int((n - 1) / 2)])

### FIXED CODE ###

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

b = sorted(a)
m1 = b[n // 2]
m2 = b[n // 2 - 1]

for num in a:
    if(num < m1):
        print(m1)
    else:
        print(m2)
### BUGGY CODE ###

print(sum(range(int(input()))))


### FIXED CODE ###

print(sum(range(int(input()))))
### BUGGY CODE ###

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

cities_prefec = {}
pref_ids = []
years = []

for i in range(M):
    prefec_id, year = map(int, input().split())

    pref_ids.append(prefec_id)
    years.append(year)

    if prefec_id in cities_prefec:
        bisect.insort(cities_prefec[prefec_id], year)
    else:
        cities_prefec[prefec_id] = [year]

for i in range(M):
    p_id = pref_ids[i]
    cn = bisect.bisect_left(cities_prefec[p_id], years[i]) + 1
    print("{0:0>6}{1:0>6}".format(p_id, cn))


### FIXED CODE ###

if __name__ == "__main__":
    _, M = map(int, input().split())
    
    outputs = [0 for _ in range(M)]
    cities = {}

    for i in range(M):
        pref, year = map(int, input().split())
        
        if pref not in cities:
            cities[pref] = {}

        cities[pref][year] = i

    for p in cities:
        city_years = list(cities[p].keys())
        city_years.sort()

        for i, cy in enumerate(city_years):
            outputs[cities[p][cy]] = "{:06}{:06}".format(p, i + 1)

    for line in outputs:
        print(line)
### BUGGY CODE ###

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

point=[]
answer=10**19
for i in range(N):
  point.append(list(map(int,input().split())))
  
for left in range(N):
  for right in range(N):
    if point[right][0]<point[left][0]:
      continue
    for ceil in range(N):
      for bottom in range(N):
        if point[bottom][1] > point[ceil][1]:
          continue
        count=0
        for i in range(N):
          x=point[i][0]
          y=point[i][1]
          if point[left][0]<=x and x<=point[right][0] and point[bottom][1]<=y and y<=point[ceil][1]:
            count+=1
        if count>=K:
          answer=min(answer,(point[right][0]-point[left][0])*(point[ceil][1]-point[bottom][1]))
     
          
print(answer)

### FIXED CODE ###

#https://atcoder.jp/contests/abc075/submissions/2242350
N,K=map(int,input().split())

points=[tuple(map(int,input().split())) for i in range(N)]
answer=10**19
sortx=sorted(points)
numberx = list(enumerate(sortx))

#n-k+1以降を左の頂点とすると点の数が明らかに足りない
for left,(x1,y1) in numberx[:N-K+1]:
  #left+K-1以降を右の頂点にしないと間に足りる点の数が入ってない
  for right,(x2,y2) in numberx[left+K-1:]:
    dx=x2-x1
    #left-rightの間でyについてsort
    sorty=sorted(y for x,y in sortx[left:right+1])
    #K個点を入れた状態で面積を求める
    for y3,y4 in zip(sorty,sorty[K-1:]):
      if y3<=y1 and y3<=y2 and y4>=y1 and y4>=y2:
        answer=min(answer,dx*(y4-y3))
         
print(answer)
### BUGGY CODE ###

N=int(input())
if N==0:
    print("Yes")
    exit()

P=[]
M=[]
for i in range(N):
    s=input()
    f=0
    m=0
    cnt=0
    for j in range(len(s)):
        if s[j]=="(":
            cnt+=1
        else:
            cnt-=1
            if cnt<m:
                m=cnt
    if cnt>=0:
        P.append([m,cnt])
    else:
        M.append([m-cnt,-cnt])
P.sort(reverse=True)
M.sort(reverse=True)
#print(P)
#print(M)
SUM=0
for i,j in P:
    SUM+=j
for i,j in M:
    SUM-=j
if SUM!=0:
    print("No")
    exit()

SUMP=0
for i,j in P:
    if SUMP>=(-i):
        SUMP+=j
    else:
        print("No")
        exit()
        
SUMM=0
for i,j in M:
    if SUMM>=(-i):
        SUMM+=j
    else:
        print("No")
        exit()
print("Yes")

### FIXED CODE ###

N=int(input())
if N==0:
    print("Yes")
    exit()

P=[]
M=[]
for i in range(N):
    s=input()
    f=0
    m=0
    cnt=0
    for j in range(len(s)):
        if s[j]=="(":
            cnt+=1
        else:
            cnt-=1
            if cnt<m:
                m=cnt
    if cnt>=0:
        P.append([m,cnt])
    else:
        M.append([m-cnt,-cnt])
P.sort(reverse=True)
M.sort(reverse=True)
#print(P)
#print(M)
SUM=0
for i,j in P:
    SUM+=j
for i,j in M:
    SUM-=j
if SUM!=0:
    print("No")
    exit()

SUMP=0
for i,j in P:
    if SUMP>=(-i):
        SUMP+=j
    else:
        print("No")
        exit()
        
SUMM=0
for i,j in M:
    if SUMM>=(-i):
        SUMM+=j
    else:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

n,k=map(int,input().split())
#0-indexed
p=[i-1 for i in list(map(int,input().split()))]
c=list(map(int,input().split()))
#1回以上K回以下
ansF=-1000000000000000000
for i in range(n):
    #すでに辿ったもの
    check=[False]*n
    #辿った順番
    turns=[]
    #今
    now=i
    while check[now]==False:
        check[now]=True
        turns.append(now)
        now=p[now]
    #答え(今の)
    ans=0
    #kのうち何回分
    #更新を毎回行う
    spare=turns.index(now)
    if spare>=k:
        for j in range(k):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    for j in range(spare):
        ans+=c[turns[j]]
        ansF=max(ans,ansF)
    turns=turns[spare:]
    spare=k-spare
    #サイクルの長さ
    l=len(turns)
    #サイクルの和(あまりも)
    #サイクルどこで止めるか
    x=0
    for j in range(l):
        x+=c[turns[j]]
    #そもそもサイクル回らない場合
    if spare<=l:
        for j in range(spare):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    #サイクル回した方が良い場合もある
    #最後のサイクルは回さない方が良いパターンも
    if x>=0:
        ans+=(x*(spare//l-1))
        ansF=max(ans,ansF)
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        for j in range(spare%l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
    #サイクル回さない方がいい場合
    else:
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
print(ansF)


### FIXED CODE ###

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

result = -float('inf')
for i in range(N):
    p = P[i] - 1
    c = C[p]
    k = K - 1
    t = c
    while p != i and k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    if k == 0 or c <= 0:
        result = max(result, t)
        continue
    l = K - k
    c = c * (K // l - 1)
    k = K - (K // l - 1) * l
    t = c
    while k != 0:
        p = P[p] - 1
        c += C[p]
        t = max(t, c)
        k -= 1
    result = max(result, t)
print(result)
### BUGGY CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def unable():
    print(-1)
    exit()

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

from heapq import heappush, heappop
h = []
for i in range(n):
    if a[i]>b[i]:
        unable()
    else:
        heappush(h, (-b[i], i))

ans = 0
while h:
    _, i = heappop(h)
    cnt, mod = divmod(b[i]-a[i],b[i-1]+b[(i+1)%n])
    if cnt == 0:
        if mod != 0:
            unable()
    else:
        ans += cnt
        b[i] = a[i]+mod
        heappush(h, (-b[i], i))
print(ans)

### FIXED CODE ###

import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

def unable():
    print(-1)
    exit()

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

from heapq import heappush, heappop
h = []
base = 10**6
for i in range(n):
    if a[i]>b[i]:
        unable()
    else:
        heappush(h, -(b[i]*base+i))

ans = 0
while h:
    k = heappop(h)
    i = -k%base
    cnt, mod = divmod(b[i]-a[i],b[i-1]+b[(i+1)%n])
    if cnt == 0:
        if mod != 0:
            unable()
    else:
        ans += cnt
        b[i] = a[i]+mod
        heappush(h, -(b[i]*base+i))
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
costs = [0] * n
costs[1] = abs(h_list[0] - h_list[1])
start = 0
for i in range(2, n):
    tmp = []
    v = h_list[i]
    start = i-k if i-k>=0 else 0
    for l in range(start, i):
        tmp.append(abs(v - h_list[l])+costs[l])
        if abs(v - h_list[l]) == 0:
            break
    costs[i] = min(tmp)
print(costs[-1])


### FIXED CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
costs = [0] * n
costs[1] = abs(h_list[0] - h_list[1])
start = 0
for i in range(2, n):
    tmp = []
    v = h_list[i]
    start = max(0, i-k)
    costs[i] = min(abs(v - h_j) + c for h_j, c in zip(h_list[start:i], costs[start:i]))
    # for l in range(start, i):
    #     tmp.append(abs(v - h_list[l])+costs[l])
    #     if abs(v - h_list[l]) == 0:
    #         break
    # costs[i] = min(tmp)
print(costs[-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in range(1,n+1):
    print(a.count(i))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
for i in range(1,n+1):
    print(c[i])
### BUGGY CODE ###

def maxprint(A,i):
    a = list(A)
    a.pop(i)
    print(max(a))

N = int(input())
A = tuple(int(input()) for _ in range(N))


for i in range(N):
    maxprint(A,i)

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
m1,m2,*_ = sorted(A)[::-1]

for i in A:
    if m1 == i:
        print(m2)
    else:
        print(m1)
### BUGGY CODE ###

n = int(input())
c = [int(input()) for i in range(n)]
dp = [1 for i in range(2*(10**5)+1)]
dp2 = [-1 for i in range(2*(10**5)+1)]
dp3 = [0 for i in range(2*(10**5)+1)]

ans = 1

def count(s):
  memo = {}
  res = 1
  for i in range(len(s)):
    if s[i] not in memo:
      memo[s[i]] = 1
    else:
      memo[s[i]] += 1
  for i in memo:
    res = res*2**(memo[i]-1)
  return res


dp2[c[0]] = 0
dp3[c[0]] += 1
#print("dp",dp)
#print("dp2",dp2)
     
for i in range(1,n):
  
  if c[i] != c[i-1]:
    if dp2[c[i]] == -1:
      dp2[c[i]] = i
      dp3[c[i]] += 1
    else:
      dp[c[i]] = count(c[dp2[c[i]]:i])*dp[c[i]]*(dp3[c[i]])
      ans += dp[c[i]]
      ans = ans % 1000000007 
      dp3[c[i]] += 1
      
      dp2[c[i]] = i
#  print(i,"dp",dp)
#  print(i,"dp2",dp2)
#  print(i,ans)
print(ans)

### FIXED CODE ###

n = int(input())
cc = [int(input()) for i in range(n)]
c = [cc[0]]
for i in range(1,n):
  if cc[i] != cc[i-1]:
    c.append(cc[i])

n = len(c)
dp = [0 for i in range(n)]
pos_dp = [-1 for i in range(2*10**5+1)]

dp[0] = 1
pos_dp[c[0]] = 0
     
for i in range(1,n):
  if pos_dp[c[i]]!=-1:
    dp[i] = (dp[i-1] + dp[pos_dp[c[i]]])%1000000007
  else:
    dp[i] = dp[i-1] 
  pos_dp[c[i]] = i

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

from collections import defaultdict
N, P = map(int,input().split())
S = input()

if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    S = int(S)
    primdic = defaultdict(int)
    for i in range(1,N+1):
        # i~右端までの数字のmodPをキーにする
        primdic[(S%pow(10,i))%P] += 1
    # 文字なしの時はあまり0なので
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-1)//2
print(ans)

### FIXED CODE ###

from collections import defaultdict
N, P = map(int,input().split())
S = input()

if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    S = S[::-1]
    primdic = defaultdict(int)
    before = 0
    for i in range(0,N):
        now = (int(S[i])*pow(10,i,P)+before)%P
        primdic[now] += 1
        before = now
    # 文字なしの時はあまり0なので
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-1)//2
print(ans)
### BUGGY CODE ###

import math
n, k = map(int, input().split())
a = int(n/k)
if(a < 2):
    b = 0
else:
    b = math.factorial(a) // (math.factorial(a - 2) * math.factorial(2))
if(a < 3):
    c = 0
else:
    c = math.factorial(a) // (math.factorial(a - 3) * math.factorial(3))
ans = a + b * 6 + c * 6
if(k % 2 == 0):
    t = int(k / 2)
    if(a * k + t > n):
      d = a
    else:
      d = a+ 1


    if(d < 2):
        e = 0
    else:
        e = math.factorial(d) // (math.factorial(d - 2) * math.factorial(2))
    if(d < 3):
        f = 0
    else:
        f = math.factorial(d) // (math.factorial(d - 3) * math.factorial(3))
    ans += (d + e * 6 + f * 6)
print(ans)

### FIXED CODE ###

import math

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

ans = int(math.pow(int(n/k),3))

if(k % 2 == 0):
  m = int( (n+int(k/2))/ k )
  ans += int(math.pow(m,3))

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

import sys
from collections import Counter
import random
import time

n=int(input())
a=list(map(int,input().split()))
S=[sum(a[:i])for i in range(n+1)]
m=n+1
c=0
for i in range(1,m):
    for j in range(i):
        if(S[i]==S[j]):c+=1
print(c)

### FIXED CODE ###

import sys
from collections import Counter
import random
import numpy as np
import time

n=int(input())
a=list(map(int,input().split()))
S=[0]
for i in range(n):
    S.append(S[i]+a[i])
    
S.sort()
c=0
ch=0
for i in range(len(S)-1):
    if(S[i]!=S[i+1]):
        ch+=1
        c+=(ch*(ch-1))//2
        ch=0
    else:ch+=1
if(ch!=0):
    ch+=1
    c+=(ch*(ch-1))//2
print(c)
### BUGGY CODE ###

from collections import deque
import copy

h,w=map(int,input().split())
maze1=[]
for _ in range(h):
  s=list(input())
  maze1.append(s)
  
def maze_solve(maze,sy,sx,gy,gx):
  Inf=float(inf)
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  
  while qu:
    y,x=qu.popleft()
    
    T=maze[y][x]
    for i in ([1,0],[-1,0],[0,1],[0,-1]):
      ny=y+i[0]
      nx=x+i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
        if maze[ny][nx]=='.':
          maze[ny][nx]=T+1
          qu.append([ny,nx])
        elif maze[ny][nx]>T+1:
          maze[ny][nx]=T+1
          qu.append([ny,nx])
          
  if maze[gy][gx]!='.':
    return maze[gy][gx]
  else:
    return -Inf
  
inf=float('inf')
ans=-inf
for i in range(h):
  for j in range(w):
    if maze1[i][j]=='.':
      for x in range(h):
        for y in range(w):
          if maze1[x][y]=='.':
            maze2=copy.deepcopy(maze1)
            
            ans=max(ans,maze_solve(maze2,i,j,x,y))
            
            
print(ans)
  

### FIXED CODE ###

from collections import deque
import copy

h,w=map(int,input().split())
Inf=float('inf')
maze1=[]
for _ in range(h):
  s=list(input())
  for u in range(w):
    if s[u]=='.':
      s[u]=Inf
  maze1.append(s)
  
def maze_solve(maze,sy,sx):
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  
  while qu:
    y,x=qu.popleft()
    
    T=maze[y][x]
    for i in ([1,0],[-1,0],[0,1],[0,-1]):
      ny=y+i[0]
      nx=x+i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
        
        if maze[ny][nx]>T+1:
          maze[ny][nx]=T+1
          qu.append([ny,nx])
          
  ans=-Inf
  for i in range(h):
    for j in range(w):
      if maze[i][j]!='#' and maze[i][j]!=Inf:
        ans=max(ans,maze[i][j])
  return ans
  

ans=-Inf
for i in range(h):
  for j in range(w):
    if maze1[i][j]!='#':
      maze2=copy.deepcopy(maze1)
      ans=max(ans,maze_solve(maze2,i,j))
            
            
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
P=[int(a)-1 for a in input().split()]
C=[int(a) for a in input().split()]
ans=-10**30
for si in range(N):
  x=si
  S=[]
  tot=0
  while True:
    x=P[x]
    S.append(C[x])
    tot+=C[x]
    if x==si:
      break
  L=len(S)
  t=0
  for i in range(L):
    t+=S[i]
    if i+1>K:
      break
    now=t
    if tot>0:
      e=(K-i-1)//L
      now+=tot*e
    ans=max(ans,now)
    
print(ans)


### FIXED CODE ###

N,K=map(int,input().split())
P=[int(a)-1 for a in input().split()]
C=[int(a) for a in input().split()]
ans=-float("inf")
for si in range(N):
  x=si
  S=[]
  tot=0
  while True:
    x=P[x]
    S.append(C[x])
    tot+=C[x]
    if x==si:
      break
  L=len(S)
  t=0
  for i in range(L):
    t+=S[i]
    if i+1>K:
      break
    now=t
    if tot>0:
      e=(K-i-1)//L
      now+=tot*e
    ans=max(ans,now)
    
print(ans)
### BUGGY CODE ###

import itertools
import heapq
import sys
readline = sys.stdin.readline
# readlines = sys.stdin.readlines
N = int(readline())
#ls = list(map(int, readline().split()))
ls = list(map(lambda x: int(x) * (-1), readline().split()))
#ls *= 100
#N *= 100
heapq.heapify(ls)
ans = 0
# n_comb = N * (N-1) * (N-2) / 6

import copy
copy_ls = copy.deepcopy(ls)
for i in range(N):
    max1 = -(heapq.heappop(ls))
    copy_ls1 = copy.deepcopy(ls)
    #print(ls)
    for j in range(N-i-1):
      # print(j, ls)
      max2 = -(heapq.heappop(ls))
      for _ in range(N-i-j-2):
        max3 = -(heapq.heappop(ls))
        if (max1 < max2 + max3):
          #print(max1, max2, max3)
          ans += 1
        else:
          # print('break')
          ls = copy.deepcopy(copy_ls1)
          heapq.heappop(ls)
          break
      ls = copy.deepcopy(copy_ls1)
      heapq.heappop(ls)
      copy_ls1 = copy.deepcopy(ls)
    
    # print('loop end')    
    ls = copy.deepcopy(copy_ls)
    heapq.heappop(ls)
    copy_ls = copy.deepcopy(ls)

print(ans)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
N = int(input())
ls = list(map(int, input().split()))
ls.sort()

ans = 0
for i in range(N-2):
  a = ls[i]
  for j in range(i+1, N-1):
    b = ls[j]
    pos = bisect.bisect_left(ls, a+b)
    ans += pos - j - 1
print(ans)
### BUGGY CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = input()
    l = len(s)

    cnt = [0 for _ in range(2019)]
    cnt[0] += 1
    dec = 1
    num = 0
    for i in reversed(s):
        num += int(i) * dec
        num%=2019
        dec *= 10
        cnt[num] += 1

    ans = 0
    for c in cnt:
        ans += c * (c - 1) // 2

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    s = input()

    cnt = [0 for _ in range(2019)]
    cnt[0] += 1
    dec = 1
    num = 0
    for i in reversed(s):
        num += int(i) * dec
        num %= 2019
        dec *= 10
        dec %= 2019
        cnt[num] += 1

    ans = 0
    for c in cnt:
        ans += c * (c - 1) // 2

    print(ans)


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

N,M = list(map(int,input().split()))
a_list = list(map(int,input().split()))
bc_list = []
for _ in range(M):
    b,c = list(map(int,input().split()))
    bc_list.append((b,c))

a_list = sorted(a_list)
bc_list = sorted(bc_list,key=lambda x: x[1],reverse=True)

count = 0
b_list = []
for b,c in bc_list:
    if count >= N:
        break
    for _ in range(b):
        b_list.append(c)
        
for i,a in enumerate(a_list):
    if i >= len(b_list):
        break
    
    if a < b_list[i]:
        a_list[i] = b_list[i]
    else:
        break
print(sum(a_list))

### FIXED CODE ###

N,M = list(map(int,input().split()))
a_list = list(map(int,input().split()))
bc_list = []
for _ in range(M):
    b,c = list(map(int,input().split()))
    bc_list.append([b,c])

a_list = sorted(a_list)
bc_list = sorted(bc_list,key=lambda x: x[1],reverse=True)

tmp = 0
for i,a in enumerate(a_list):
    if tmp >= len(bc_list):
        break
    
    if a < bc_list[tmp][1]:
        bc_list[tmp][0] -= 1
        a_list[i] = bc_list[tmp][1]
    else:
        break

    if bc_list[tmp][0] == 0:
        tmp += 1
print(sum(a_list))