Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


class MyHeap(object):
    def __init__(self, x):
        self.heap = [self._encode(e) for e in x]
        heapq.heapify(self.heap)

    def push(self, value):
        heapq.heappush(self.heap, self._encode(value))

    def pop(self):
        return self._decode(heapq.heappop(self.heap))

    def _encode(self, x):
        a, b, i = x
        return [-b, a, i]

    def _decode(self, x):
        b, a, i = x
        return [a, -b, i]

    def __len__(self):
        return len(self.heap)


def solve(N: int, A: "List[int]", B: "List[int]"):

    lh = MyHeap([])
    for i in range(N):
        lh.push((A[i], B[i], i))

    count = 0
    while len(lh) > 0:
        a, b, i = lh.pop()
        if B[i]-B[(i+1) % N]-B[(i-1) % N] > 0:
            count += B[i]//(B[(i+1) % N]+B[(i-1) % N])
            B[i] %= (B[(i+1) % N]+B[(i-1) % N])
            if A[i] < B[i]:
                lh.push([A[i], B[i], i])
        else:
            continue
    for i in range(N):
        if A[i] != B[i]:
            print(-1)
            return

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import heapq


def solve(N: int, A: "List[int]", B: "List[int]"):

    count = 0
    flag = True
    while flag:
        flag = False
        for i in range(N):
            a, b, c = B[i-1], B[i], B[(i+1) % N]
            if b > A[i] and b > a+c:
                d, m = divmod(b-A[i], a+c)
                if m == 0:
                    B[i] = A[i]
                    count += d
                else:
                    d, m = divmod(b, a+c)
                    count += d
                    B[i] = m
                flag = True
    # print(*A)
    # print(*B)
    if A != B:
        count = -1

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


if __name__ == '__main__':
    main()
N = int(input())
SAC = 0
SWA = 0
STLE = 0
SRE = 0
for i in range(N):
  tmp = imput()
  if tmp == 'AC':
    SAC += 1
  elif tmp == 'WA':
    SWA += 1
  elif tmp == 'TLE':
    STLE += 1
  elif tmp == 'RE':
    SRE += 1

print("AC x " + str(SAC))
print("WA x "+ str(SWA))
print("TLE x "+str(STLE))
print("RE x "+str(SRE))


### FIXED CODE ###

N = int(input())
SAC = 0
SWA = 0
STLE = 0
SRE = 0
for i in range(N):
  tmp = input()
  if tmp == 'AC':
    SAC += 1
  elif tmp == 'WA':
    SWA += 1
  elif tmp == 'TLE':
    STLE += 1
  elif tmp == 'RE':
    SRE += 1

print("AC x " + str(SAC))
print("WA x "+ str(SWA))
print("TLE x "+str(STLE))
print("RE x "+str(SRE))
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache, reduce
from operator import xor
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


color, depth, graph = [], [], {}
def func(v, d, c):
    if not color[v]:
        color[v] = c
    if depth[v] >= d or d == 0:
        return

    for u in graph[v]:
        func(u, d - 1, c)


def main():
    global color, depth, graph
    N, M = map(int, input().split())
    graph = [[] for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        graph[a].append(b)
        graph[b].append(a)

    Q = int(input())
    q = []
    for _ in range(Q):
        v, d, c = map(int, input().split())
        q.append((v - 1, d, c))

    color = [0] * N
    depth = [0] * N
    for i in range(Q - 1, -1, -1):
        func(q[i][0], q[i][1], q[i][2])
    print(*color, sep="\n")

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")


def main():
    N = int(input())
    a_list = list(sorted(list(map(int, input().split()))))
    print(sum([a_list[-i * 2 - 2] for i in range(0, N)]))


if __name__ == '__main__':
    main()
S,f=__import__('collections').deque(input()),0
for _ in range(int(input())):
	T=input()
	if'2'>T:f=1-f
	else:S.insert(0 if(T[2]<'2')^f else len(S),T[4])
if f:S.reverse()
print(*S,sep='')

### FIXED CODE ###

S,f=__import__('collections').deque(input()),0
for _ in range(int(input())):
	T=input()
	if T<'2':f=1-f
	else:(S.appendleft if (T[2]<'2')^f else S.append)(T[4])
if f:S.reverse()
print(*S,sep='')
N=int(input())

def factoring(M,n=2):
    for i in range(n,int(M**0.5)+1):
        if M%i==0:
            ret = factoring(M//i,i)
            ret[i] = ret.get(i,0)+1
            return ret
    return {M:1}

p = {}
for i in range(2,N+1):
    for k,v in factoring(i).items():
        p[k] = p.get(k,0)+v

c = [0]*4
for n in p.values():
    if n>=24:c[3]+=1
    elif n>=14:c[2]+=1
    elif n>=4:c[1]+=1
    elif n>=2:c[0]+=1

ans = 0
ans += p[2]>=74
ans += c[3]*(sum(c)-1)
c[2] += c[3]
ans += c[2]*(c[1]+c[2]-1)
c[1] +=c[2]
ans += c[0]*c[1]*(c[1]-1)//2
ans += c[1]*(c[1]-1)*(c[1]-2)//2
print(ans)

### FIXED CODE ###

N = int(input())

def get_soinsu(n):
    if n ==1:
        return
    for p in soinsu.keys():
        if n%p == 0:
            soinsu[p] += 1
            get_soinsu(n//p)
            break
    else:
        soinsu[n] = 1

soinsu = {}
for i in range(2,N+1):
    get_soinsu(i)

tmp3 = soinsu.values()
    
#素因数が(74)個の数の選び方
num_74 = len([tmp for tmp in tmp3 if tmp >= 74])

#素因数が(2,24)個の数の選び方
num_24_2 = len([tmp for tmp in tmp3 if tmp >= 24]) * (len([tmp for tmp in tmp3 if tmp >= 2])-1)

#素因数が(4,14)個の数の選び方
num_14_4 = len([tmp for tmp in tmp3 if tmp >= 14]) * (len([tmp for tmp in tmp3 if tmp >= 4])-1)

#素因数が(2,4,4)個の数の選び方
tmp2 = len([tmp for tmp in tmp3 if tmp >= 4])
num_4_4_2 = max(0,tmp2*(tmp2-1)*(len([tmp for tmp in tmp3 if tmp >= 2])-2)//2)

print(num_74 + num_24_2 + num_14_4 + num_4_4_2)
def main():
    A, B, C, D = input()
    for i in range(2):
        ans = int(A)
        if i == 0:
            ans += int(B)
        else:
            ans -= int(B)
        for j in range(2):
            if j == 0:
                ans += int(C)
            else:
                ans -= int(C)
            for k in range(2):
                if k == 0:
                    ans += int(D)
                else:
                    ans -= int(D)
                
                if ans == 7:
                    l = [i, j, k]
        
    op = []
    for ele in l:
        if ele == 0:
            op.append('+')
        else:
            op.append('-')
    print(A + op[0] + B + op[1] + C + op[2] + D + '=7')
                    
                
                
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    A, B, C, D = input()
    for i in range(2**3):
        op = ['+', '+', '+']
        for j in range(len(op)):
            if (i >> j) & 1:
                op[j] = '-'
        if eval(A + op[0] + B + op[1] + C + op[2] + D) == 7:
            print(A + op[0] + B + op[1] + C + op[2] + D + '=7')
            break
    
                
                
if __name__ == '__main__':
    main()
n, x = list(map(int, input().split()))
L = list(map(int, input().split()))
length = 0
i = 0
while x >= length and n >= i:
    length += L[i]
    i += 1
print(i)

### FIXED CODE ###

n, x = list(map(int, input().split()))
L = list(map(int, input().split()))
length = 0
i = 0
count = 1
while n > i:
    length += L[i]
    if length <= x:
        count += 1
    i += 1
print(count)
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    print((cmb(m,k)-cmb(m-2-ma,k-1))%mod)

### FIXED CODE ###

import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 10**5+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

ma=0
dic={}
for i in range(m):
    if not a[i] in dic:
        dic[a[i]]=i
    else:
        ma=i-dic[a[i]]-1

for k in range(1,m+1):
    if k==1:
        print(n)
        continue
    tmp=cmb(m,k)
    if m-2-ma>=k-1:
        tmp-=cmb(m-2-ma,k-1)
    print(tmp%mod)
a,b,c,d = map(int,input().split())
u = b - a + 1
import math
div_c = set()
div_d = set()
for i in range(1,int(math.sqrt(c))+):
    if c % i == 0:
        div_c.add(i)
for i in range(1,int(math.sqrt(d))+1):
    if d % i == 0:
        div_d.add(i)
gcd = max(list(div_c & div_d))
cd = c*d/gcd    
n_c = b//c - (a-1)//c
n_d = b//d - (a-1)//d
n_cd = b//(cd) - (a-1)//(cd)
print(int(u - n_c - n_d + n_cd))

### FIXED CODE ###

a,b,c,d = map(int,input().split())
u = b - a + 1
from fractions import gcd
cd = c*d//gcd(c,d)
n_c = b//c - (a-1)//c
n_d = b//d - (a-1)//d
n_cd =b//cd - (a-1)//cd
print(int(u - n_c - n_d + n_cd))
from operator import itemgetter

N,M = map(int,input().split())
cities = [ 0 for _ in range(M) ]

for i in range(M):
    p,y = map(int,input().split())
    cities[i] = [p,y,i]
cities = sorted(cities,key=itemgetter(1))
cities = sorted(cities,key=itemgetter(0))

out = ["*" for _ in range(M)]

beforeCity = cities[0][0]
cityCnt = 1
for i in range(M):
    if beforeCity != cities[i][0]:
        cityCnt = 1
    if len(str(cities[i][0])) < 6:
        cityNo1 = "0"*(6 - len(str(cities[i][0])))+str(cities[i][0])
    if len(str(cityCnt)) < 6:
        cityNo2 = "0"*(6 - len(str(cityCnt)))+str(cityCnt)
    out[cities[i][2]] = cityNo1+cityNo2
    cityCnt += 1
for a in out:
    print(a)

### FIXED CODE ###

import sys
import os
from operator import itemgetter

N,M = map(int,input().split())
cities = [ 0 for _ in range(M) ]

for i in range(M):
    p,y = map(int,input().split())
    cities[i] = [p,y,i]
cities = sorted(cities,key=itemgetter(1))
cities = sorted(cities,key=itemgetter(0))

out = ["*" for _ in range(M)]
beforeCity = cities[0][0]
cityCnt = 1
for i in range(M):
    curCity = cities[i][0]
    if beforeCity != curCity:
        cityCnt = 1
    cityNo1 = str(curCity).zfill(6)
    cityNo2 = str(cityCnt).zfill(6)
    out[cities[i][2]] = cityNo1+cityNo2
    beforeCity = curCity
    cityCnt += 1

for a in out:
    print(a)
# -*- coding:utf-8 -*-
A=int(input())
B=int(input())
if A+B==3:
    print(3)
elif A+B=4:
    print(2)
else:
    print(1)

### FIXED CODE ###

# -*- coding:utf-8 -*-
A=int(input())
B=int(input())
if A+B==3:
    print(3)
elif A+B==4:
    print(2)
else:
    print(1)
N = int(input())

nine = [9**i for i in range(7, 0, -1)]
six = [6**i for i in range(8, 0, -1)]
tmp = {}

def f(n):
  if(n < 6):
    return n
  if(n in tmp):
    return tmp[n]
  
  m = 1e9+7
  if(n >= 9):
    mn = max(x for x in nine if x <= n)
    if(n%mn == 0):
      m = min(m, n//max_nine)
    else:
      m = min(m, f(n-mn)+1)
  ms = max(x for x in six if x <= n)
  if(n%ms == 0):
    m = min(m, n//ms)
  tmp[n] = min(m, f(n-ms)+1)
  return tmp[n]
print(f(N))

### FIXED CODE ###

N = int(input())

ans = 10**9+7
for i in range(N+1):
  j = N-i
  cnt = 0
  while i > 0:
    cnt += i%6
    i //= 6
  while j > 0:
    cnt += j%9
    j //= 9
  ans = min(ans, cnt)
print(ans)
input_N = input('>>'  )

print ('ABC') + input_N

### FIXED CODE ###

N = int(input())
print ('ABC%d' %N)
x = int(input())

if x = 0:
  print("1")
else:
  print("0")

### FIXED CODE ###

x = int(input())

if x >= 1:
  print(0)
else:
  print(1)
import itertools
N, M = list(map(int, input().split()))
X = list(map(int, input().split()))
X.sort()

if N <= M:
    mar = [X[i+1] - X[i] for i in range(len(M-1))]
    mar.sort()
    print(sum([mar[i] for i in range(M-N)]))
else:
    print(0)


### FIXED CODE ###

import itertools
N, M = list(map(int, input().split()))
X = list(map(int, input().split()))
X.sort()

if N < M:
    mar = [abs(X[i+1] - X[i]) for i in range(M-1)]
    mar.sort()
    print(sum([mar[i] for i in range(M-N)]))
else:
    print(0)
#! /usr/bin/env python3
# -*- coding: utf-8 -*-


nnk = list(map(lambda x: int(x), input().split(" ")))
n = nnk[0]
k = nnk[1]

hs = [int(input()) for l in range(n)]
hs.sort()

num = n - k + 1

hmmm = []
for l in range(num):
    hmmm.append(hs[k+l-1] - hs[l])

hmmm.sort()
print(hmm[0])

### FIXED CODE ###

nnk = input().split(" ")
n = int(nnk[0])
k = int(nnk[1])

hs = [int(input()) for l in range(n)]
hs.sort()

hmmm = []
for m in range(n-k+1):
    hmmm.append(hs[k+m-1] - hs[m])

hmmm.sort()
print(hmmm[0])
from math import sqrt
N, D = map(int, input().split())
count = 0
for i in range(N):
    P, Q = map(int, input().split())
    dis = ((P**2)+(Q**2))**0.5
    if dis >= D:
        count+=1
print(count)

### FIXED CODE ###

X = int(input())
if X>=30:
    print("Yes")
else:
    print("No")
d, n = map(int, input().split())

print(100 ** d * n　if n <= 99 else 100 ** d * (n + 1))

### FIXED CODE ###


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

print(100 ** d * n if n <= 99 else 100 ** d * (n + 1))
H,W=map(int,input().split())
A=[[int(i) for i in input().split()] for j in range(H)]
B=[[int(i) for i in input().split()] for j in range(H)]
dp=[[0 for j in range(W)] for i in range(H)]
M=80*80*2+1
dp[0][0]=1<<(abs(A[0][0]-B[0][0])+M)

for i in range(H):
    for j in range(W):
        dij=abs(A[i][j]-B[i][j])
        if i>0:
            dp[i][j]|=dp[i-1][j]<<dij
            dp[i][j]|=dp[i-1][j]>>dij
        if j>0:
            dp[i][j]|=dp[i][j-1]>>dij
            dp[i][j]|=dp[i][j-1]<<dij
ans=[]
for i in range(M):
    if (1<<i)&dp[-1][-1]!=0:
        ans.append(abs(i-M))
print(min(ans))

### FIXED CODE ###

H,W=map(int,input().split())
A=[[int(i) for i in input().split()] for j in range(H)]
B=[[int(i) for i in input().split()] for j in range(H)]
dp=[[0 for j in range(W)] for i in range(H)]
M=161*161
dp[0][0]|=1<<(A[0][0]-B[0][0]+M)
dp[0][0]|=1<<(-A[0][0]+B[0][0]+M)

for i in range(H):
    for j in range(W):
        dij=abs(A[i][j]-B[i][j])
        if i>0:
            dp[i][j]|=dp[i-1][j]<<dij
            dp[i][j]|=dp[i-1][j]>>dij
        if j>0:
            dp[i][j]|=dp[i][j-1]>>dij
            dp[i][j]|=dp[i][j-1]<<dij
ans=[]
for k in range(2*M+1):
    if (1<<k)&dp[-1][-1]!=0:
        ans.append(abs(k-M))
print(min(ans))
a,b,t = map(int(input().split()))
ans = t//a
print(ans*b)

### FIXED CODE ###

a,b,t = map(int,input().split())
ans = t//a
print(ans*b)
AC, BC, MC = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
M = [tuple(map(int, input().split())) for _ in range(MC)]

ans = min(A) + min(B)
for x, y, c in M:
    ans = min(ans, A[x - 1] + B[x - 1] - c)
print(ans)

### FIXED CODE ###

AC, BC, MC = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
M = [tuple(map(int, input().split())) for _ in range(MC)]

ans = min(A) + min(B)
for x, y, c in M:
    ans = min(ans, A[x - 1] + B[y - 1] - c)
print(ans)
a,b,m = map(int,input().split())
a_li = list(map(int,input().split()))
b_li = list(map(int,input().split()))
cost = [min(a_li) + min(b_li)]

for i in range(m):
  x,y,c = map(int,input().split())
  price = a_li[x-1] + a_li[y-1] - c
  cost.append(price)
print(min(cost))

### FIXED CODE ###

A, B, M = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
X = [list(map(int, input().split())) for i in range(M)]

ans = [min(a) + min(b)]
for x in X:
    a_idx, b_index, c = x
    ans.append(a[a_idx - 1] + b[b_index - 1] - c)

print(min(ans))
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

s = input()
 
i = 0
 
while i <= len(s):
	print(s[i], end="")
	i += 2
 
print()

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

s = input()
 
i = 0
 
while i <= len(s)-1:
	print(s[i], end="")
	i += 2
 
print()
a, b = map(int,raw_input().split())

if a<b:
  print 'a < b'
else if a>b:
  print 'a > b'
else:
  print 'a == b'

### FIXED CODE ###

a,b=map(int,raw_input().split())

if a>b:
  print 'a > b'
elif a<b:
  print 'a < b'
else:
  print 'a == b'
H, W = map( int, input().split() )
s = [ [ map( str, input().split() ) ] for i in range(H) ] 
for i in range(H) : 
    for j in range(W) : 
       if s[i][j] == "snuke" : 
           w = chr( i + ord( "A" ) )
           h = i + 1
           exit()
print( w + str( h ) )

### FIXED CODE ###

H, W = map( int, input().split() )
s = [ list( map( str, input().split() ) ) for i in range(H) ] 
for i in range(H) : 
    for j in range(W) : 
       if s[i][j] == "snuke" : 
           w = chr( j + ord( "A" ) )
           h = i + 1
           print( w + str( h ) )
           exit()
a,b = input().split()
x,y = int(input().split())
k = input()

if a == k :
  print(x-1,y)
elif b == k :
  print(x,y-1)
else:
  print(x,y)


### FIXED CODE ###

S,T = input().split()
A,B = map(int, input().split())
U = input()

if S==U:
    A -= 1
else:
    B -= 1
print(A,B)
n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = a[i] % k

ruiseki = [0]
for i in range(n):
    ruiseki.append((a[i]+ruiseki[-1])%k)

mini = 0
dic = {}
ans = 0
for j in range(1, n+1):
    if j-k+1 > mini:
        dic[(ruiseki[mini]-mini)%k] -= 1
        mini += 1
    if (ruiseki[j-1]-(j-1))%k in dic:
        dic[(ruiseki[j-1]-(j-1))%k] += 1
    else:
        dic[(ruiseki[j-1]-(j-1))%k] = 1
    if (ruiseki[j]-j)%k in dic:
        ans += dic[(ruiseki[j]-j)%k]
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = a[i] % k

if k == 1:
    print(0)
    exit()

ruiseki = [0]
for i in range(n):
    ruiseki.append((a[i]+ruiseki[-1])%k)

mini = 0
dic = {}
ans = 0
for j in range(1, n+1):
    if j-k+1 > mini:
        dic[(ruiseki[mini]-mini)%k] -= 1
        mini += 1
    if (ruiseki[j-1]-(j-1))%k in dic:
        dic[(ruiseki[j-1]-(j-1))%k] += 1
    else:
        dic[(ruiseki[j-1]-(j-1))%k] = 1
    if (ruiseki[j]-j)%k in dic:
        ans += dic[(ruiseki[j]-j)%k]
print(ans)
# AtCoder Regular Contest 080
# C - 4-adjacent

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

oddcount=0
mod40=0
other=0

for a in alist:
    if a%2==1:
        oddcount+=1
    elif a%4==0:
        mod40+=1
    else:
        other+=1

if N==1:
    if mod40==N:
        print("Yes")
    else:
        print("No")
if N==2 or N==3:
    if mod40>0 or other==N:
        print("Yes")
    else:
        print("No")
else:
    print(np.array())


# if (N-other)%2==1:
#     if (N-other)//2 <= mod40:
#         print("Yes")
#     else:
#         print("No")

# else:
#     if (N-other)//2 < mod40:
#         print("Yes")
#     else:
#         print("No")


### FIXED CODE ###

# AtCoder Regular Contest 080
# C - 4-adjacent

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

oddcount=0
mod40=0
other=0

for a in alist:
    if a%2==1:
        oddcount+=1
    elif a%4==0:
        mod40+=1
    else:
        other+=1

if N==1:
    if mod40==N:
        print("Yes")
        exit()
    else:
        print("No")
        exit()
if N==2 or N==3:
    if mod40>0 or other==N:
        print("Yes")
        exit()
    else:
        print("No")
        exit()
# ↑ここまではあってそう。

if N%2==1:  # N>3 ,Nが奇数の時
    if (N-((other//2)*2))//2 <= mod40:
        print("Yes")
        exit()
    else:
        print("No")
        exit()

else:   # N>3 ,Nが偶数の時
    if other%2==1:  #かつ、要素が偶数である数が奇数の時  
        if (N-((other//2)*2))//2 <= mod40:
            print("Yes")
            exit()
        else:
            print("No")
            exit()
    else:
        if (N-((other//2)*2))//2 <= mod40:
            print("Yes")
            exit()
        else:
            print("No")
            exit()
n = int(input())
k = int(input())
a = list(map(int,input().split()))
asr = sorted(a)
del asr[0:n-k]
ans = sum(asr)
print(str(ans))

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
asr = sorted(a,reverse=True)
del asr[0:n-k]
ans = sum(asr)
print(str(ans))