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

n=int(input())
c=0
from itertools import combinations 
def rSubset(arr, r): 
  
    # return list of all subsets of length r 
    # to deal with duplicate subsets use  
    # set(list(combinations(arr, r))) 
    return list(combinations(arr, r)) 
for y in range(1,n+1):
    t=[]
    x=[]
    for i in range(1,int(y**0.5)):
        t.append(y)
    x=rSubset(t,3)
    for i in range(len(x)):
        if(x[i][0]**2+x[i][1]**2+x[i][2]**2+x[i][0]*x[i][1]+x[i][0]*x[i][2]+x[i][1]*x[i][2]==n):
           c=c+6
    for i in range(1,int(y**0.5)):
        for j in range(1,int(y**0.5)):
            if(3*i*i+j*j+2*i*j==y):
                if(i==j):
                  c=c+1
                else:
                   c=c+3
    print(c)
    c=0
    

### FIXED CODE ###

N = int(input())

ans = [0]*N

for i in range(1,101,1):
  for j in range(1,101,1):
    for k in range(1,101,1):
      n = i**2+j**2+k**2+i*j+j*k+k*i
      if n > N:
        continue
      else:
        ans[n-1]+=1
      
for i in range(N):
  print(ans[i])
### BUGGY CODE ###

H, W = map(int, input().split()) # 横に2個
state = [[0 if a == '.' else 1 for a in list(input())] for _ in range(H)]

checked = [[False for _ in range(W+1)] for _ in range(H+1)]
qs = []
for h in range(H):
    for w in range(W):
        if state[h][w] == 1:
            qs.append([h, w])
            checked[h][w] = True
for h in range(H+1):
    checked[h][W] = True
for w in range(W+1):
    checked[H][w] = True

c = 0
while qs:
    qqs = []
    for h,w in qs:
        checked[h][w] = True
        if 0 < h and not checked[h-1][w]:
            qqs.append([h-1, w])
        if h < H-1 and not checked[h+1][w]:
            qqs.append([h+1, w])
        if 0 < w and not checked[h][w-1]:
            qqs.append([h, w-1])
        if w < W-1 and not checked[h][w+1]:
            qqs.append([h, w+1])
    if not qqs:
        break
    c += 1
    qs = qqs

print(c)

### FIXED CODE ###

import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if len(q) == 0:
            break
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
        q = qq
        c += 1

    print(c)


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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    dp = []
    for _ in range(N):
        a = LI()
        G.append(a)
        dp.append(a)

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    print(-1)
                    return 

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if j == k or k == i:
                    continue
                if dp[i][k] == inf or dp[i][j] == inf or dp[j][k] == inf:
                    continue
                if G[i][j] == G[i][k] + G[k][j]:
                    # i->jは要らない
                    dp[i][j] = inf
    cnt = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] < inf:
                cnt += dp[i][j]
    print(cnt // 2)
main()



### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
 
DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
 
    if dp != G:
        print(-1)
        return
 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if j == k:
                    continue
                if i == k:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print(cnt // 2)
main()
### BUGGY CODE ###

n = int(input())

time = [0]+list(map(int,input().split()))+[0]
v = [0] + list(map(int,input().split()))+[0]

lines = []
t = 0
lines.append((-1,0,0))
for i in range(1,n+1):
    lines.append((t,t+time[i],v[i]))
    t+=time[i]

lines.append((t,t+1,0))
def ff(p,x):
    x1,x2,vv = p
    if x<x1:
        return vv+x1-x
    elif x>x2:
        return vv+x-x2
    else:
        return vv
def f(x):
    speed = 10**18
    for line in lines:
        speed = min(speed,ff(line,x))
    return speed 
res = 0
for a in range(2*t):
    a = a/2
    res += 0.25*(f(a)+f(a+0.5))
print(res)


### FIXED CODE ###

n = int(input())

time = [0]+list(map(int,input().split()))+[0]
v = [0] + list(map(int,input().split()))+[0]

lines = []
t = 0
lines.append((-1,0,0))
for i in range(1,n+1):
    lines.append((t,t+time[i],v[i]))
    t+=time[i]
lines.append((t,t+1,0))
def f(x):
    speed = 10**18
    for x1,x2,vv in lines:
        if x<x1:
            speed = min(speed,vv+x1-x)
        elif x>x2:
            speed = min(speed,vv+x-x2)
        else:
            speed = min(speed,vv)
    return speed
dp = [0]*(2*t)
for i in range(2*t):
    dp[i] = f(i/2)
dp.append(0)
res = 0
res = sum(dp)*2-dp[0]-dp[-1]
print(res*0.25)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq
n = int(input())
sss = [input()[:-1] for _ in range(n)]

a = []
b = []
ss = 0
ii = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    ss += s
    if s >= 0:
        a.append([-s, mi, ma, ii])
    else:
        mi = 0
        ma = 0
        s = 0
        for j in reversed(i):
            if j == ")":
                s += 1
            else:
                s -= 1
            mi = min(mi, s)
            ma = max(ma, s)
        b.append([-s, mi, ma, ii])
    ii += 1


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok1(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        kkk = 0
        for j in sss[heapq.heappop(heap)[-1]]:
            kkk += 1
            if j == "(":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


def ok(a):
    s = 0
    heap = []
    i = 0
    while True:
        while i < len(a) and a[i][1] + s >= 0:
            heapq.heappush(heap, a[i])
            i += 1
        if i < len(a) and not heap:
            print("No")
            exit()
        if not heap:
            break
        kkk = 0
        for j in reversed(sss[heapq.heappop(heap)[-1]]):
            kkk += 1
            if j == ")":
                s += 1
            else:
                s -= 1
            if s < 0:
                print("No")
                exit()


ok1(a)
ok(b)
print("Yes")


### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
n = int(input())
sss = [input()[:-1] for _ in range(n)]

a = []
b = []
ss = 0
ii = 0
for i in sss:
    mi = 0
    ma = 0
    s = 0
    for j in i:
        if j == "(":
            s += 1
        else:
            s -= 1
        mi = min(mi, s)
        ma = max(ma, s)
    ss += s
    if s >= 0:
        a.append([s, mi, ma, ii])
    else:
        mi = 0
        ma = 0
        s = 0
        for j in reversed(i):
            if j == ")":
                s += 1
            else:
                s -= 1
            mi = min(mi, s)
            ma = max(ma, s)
        b.append([s, mi, ma, ii])
    ii += 1


if ss != 0:
    print("No")
    exit()
a.sort(reverse=1, key=lambda x: x[1])
b.sort(reverse=1, key=lambda x: x[1])


def ok(a):
    s = 0
    for i, j, _, _ in a:
        if s + j < 0:
            print("No")
            exit()
        s += i

ok(a)
ok(b)
print("Yes")
### BUGGY CODE ###

import sys
input=sys.stdin.readline
from random import seed, randint

def calc(d,C,S,T):
    Last=[0]*26
    score=0
    for day,t in enumerate(T):
        t-=1
        Last[t]=day+1
        score+=S[day][t]
        for i,c in enumerate(C):
            score-=c*(day+1-Last[i])
    return score

def main():
    d=int(input())
    C=tuple(map(int,input().split()))
    S=[tuple(map(int,input().split())) for _ in range(d)]
    Ans=[0]*d
    Last=[0]*26
    
    #貪欲法
    for day in range(d):
        ans=0
        score=-float('inf')
        for t in range(26):
            TmpList=Last[:]
            tmp_score=S[day][t]
            TmpList[t]=day+1
            for i,c in enumerate(C):
                tmp_score-=c*(day+1-TmpList[i])
            if tmp_score>score:
                score=tmp_score
                ans=t+1
        Ans[day]=ans
        Last[ans-1]=day
    
    score=calc(d,C,S,Ans)
    #print(Ans)
    #print(score)
    
    #局所探索法
    m=15000
    for i in range(m):
        T=Ans[:]
        seed(i)
        d_idx=randint(0,d-1)
        q=randint(1,26)
        #print(d_idx,q)
        T[d_idx]=q
        tmp=calc(d,C,S,T)
        if tmp>score:
            score=tmp
            Ans=T[:]
    #print(Ans)
    #print(score)
    
    print(*Ans,sep='\n')
    
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
from random import seed, randint

def calc(d,C,S,T):
    Last=[0]*26
    score=0
    for day,t in enumerate(T):
        t-=1
        Last[t]=day+1
        score+=S[day][t]
        for i,c in enumerate(C):
            score-=c*(day+1-Last[i])
    return score

def main():
    d=int(input())
    C=tuple(map(int,input().split()))
    S=[tuple(map(int,input().split())) for _ in range(d)]
    T=[(i%26)+1 for i in range(d)]
    score=calc(d,C,S,T)
    Ans=T[:]
    #print(score)
    m=10000
    for i in range(m):
        seed(i)
        d_idx=randint(0,d-1)
        q=randint(1,26)
        #print(d_idx,q)
        T[d_idx]=q
        tmp=calc(d,C,S,T)
        if tmp>score:
            score=tmp
            Ans=T[:]
    #print(score)
    print(*Ans,sep='\n')
    
if __name__=='__main__':
    main()
### BUGGY CODE ###

X = int(input())
diff = 1
for i in range(2,X):
    if X % i == 0:
        diff = i
        break

s = (10 **9)//2
while True:
    A = s 
    B = s - diff
    xx = A ** 5 - B ** 5
    if xx == X:
        break
    elif xx > X:
        s = s //2
    else:
        s =  (3*s) //4
print(int(A),int(B))

### FIXED CODE ###

def main():
    X = int(input())
    for B in range(-120,121):
        for A in range(B,121):
            xx = A**5 -B ** 5
            if X ==  xx:
                print(A,B)
                return
            elif X <xx:
                break

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

import numpy as np
import copy

cubes = list(input())
cubes = list(map(int, cubes))

def removeCubes(cubeList, cnt):
    cubeArray = np.array(cubeList)
    originalList = copy.deepcopy(cubeList)
    max = 0
    resultList = []
    for i in range(0, len(cubeArray) - 1):
        if cubeArray[i] != cubeArray[i + 1]:
            cubeList.pop(i)
            cubeList.pop(i)
            resultList.append(removeCubes(cubeList, cnt + 1))
            cubeList = copy.deepcopy(originalList)
    if len(resultList) == 0:
        return cnt
    elif len(resultList) == 1:
        return resultList[0]
    else :
        maxRet = 0
        for j in range(0, len(resultList)):
            if maxRet < resultList[j]:
                maxRet = resultList[j]
        return maxRet

print(removeCubes(cubes, 0) * 2)

### FIXED CODE ###

import numpy as np
import copy

cubes = list(input())
cubes = np.array(list(map(int, cubes)))

zeroNum = 0
oneNum = 0
for i in range(0, len(cubes)):
    if cubes[i] == 0:
        zeroNum += 1
    else :
        oneNum += 1

print(min(zeroNum, oneNum) * 2)
### BUGGY CODE ###

def SS(A, K):
    sA = 0
    AA = []
    for a in A:
        sA += a
        if sA > K:
            break
        AA.append(sA)

    return AA


def main():
    N, M, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    AA = SS(A, K)
    BB = SS(B, K)
    AA = AA[::-1]

    M = max(len(AA), len(BB))

    left = 0
    right = len(BB) - 1

    while left < len(AA):
        if AA[left] + BB[right] <= K:
            m = len(AA) - left + right + 1
            if m > M:
                M = m
            left += 1
            right = len(BB) - 1
        else:
            right -= 1
            if right < 0:
                left += 1
                right = len(BB) - 1

    print(M)


main()


### FIXED CODE ###

import numpy as np

from numba import njit


@njit("i8[:](i8, i8[:], i8[:])", cache=True)
def cumsum(K, A, cA):
    for i, a in enumerate(A):
        cA[i] += cA[i - 1] + A[i]
        if cA[i] > K:
            break

    cA = cA[cA != 0]
    cA = np.append(0, cA)
    return cA


@njit("i8(i8, i8[:], i8[:])", cache=True)
def solve(K, cA, cB):
    ans = np.searchsorted(cA, K - cB, side="right") - 1
    ans += np.arange(len(cB))
    return ans.max()


N, M, K = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
B = np.array(input().split(), dtype=np.int64)

cA = np.zeros(N, dtype=np.int64)
cB = np.zeros(M, dtype=np.int64)

# np.cumsumだとoverflowする
cA = cumsum(K, A, cA)
cB = cumsum(K, B, cB)

ans = solve(K, cA, cB)
print(ans)
### BUGGY CODE ###

mini, maxi, K_ban = map(int, input().split())

num_list = [i for i in range(mini, maxi + 1)]

if (maxi - mini + 1 > 2 * K_ban):
    num_list = num_list[:K_ban] + num_list[-K_ban:]


[print(n) for n in num_list]

### FIXED CODE ###

mini, maxi, K_ban = map(int, input().split())

if (maxi - mini + 1 <= 2 * K_ban):
    ans = [i for i in range(mini, maxi + 1)]

else:
    left = [i for i in range(mini, mini + K_ban)]
    right = [i for i in range(maxi - K_ban + 1, maxi + 1)]
    
    ans = left + right
    

[print(n) for n in ans]
### BUGGY CODE ###

import itertools

number_str = '999999999'
number_int = int(number_str)

count = 0


length = len(number_str)



def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


def calc_pre(leng_pre):
    global count
    count += pow(3, leng_pre) + 3 -  3 * pow(2, leng_pre)

def calc_all(length):
    global count
    l = ['3', '5', '7']
    pre_data = set()
    for v in itertools.combinations_with_replacement(l, length):
        # print(v)
        if'3' in v and '5' in v and '7' in v:
            for vv in itertools.permutations(list(v), length):
                aaa = int(''.join(list(vv)))
                if aaa < number_int:
                    if aaa not in pre_data:
                        # print(aaa)
                        count += 1
                        pre_data.add(aaa)
                else:
                    break

if length > 3:
    for i in range(3, length):
        calc_pre(i)

calc_all(length)

print(count)

# print(pow(2, 3))

### FIXED CODE ###


ans = 0

def check(num_str):
    for i in ['7', '5', '3']:
        if i not in num_str:
            return 0
    return 1

def make_data(num, num_str):
    global ans
    if num < int(num_str):
        return
    if check(num_str):
        ans += 1

    make_data(num, num_str + '7')
    make_data(num, num_str + '5')
    make_data(num, num_str + '3')


def main():
    num = int(input())
    make_data(num, '0')

    global ans
    print(ans)


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

from numpy import zeros

s, t = input(), input()
ls, lt = len(s), len(t)

table = zeros((ls+1, lt+1))
for ss in range(ls):
    for st in range(lt):
        table[ss+1][st+1] = table[ss][st] + 1 if s[ss] == t[st] else max(table[ss+1][st], table[ss][st+1] )

ans = ""
ss, st = ls, lt
while ss * st != 0:
    if table[ss][st] == table[ss-1][st]:
        ss -= 1
    elif table[ss][st] == table[ss][st-1]:
        st -= 1

    else:
        ss -= 1
        st -= 1
        ans = s[ss] + ans

print(ans)

### FIXED CODE ###

s, t = input(), input()
ls, lt = len(s), len(t)

table = [[0] * (lt+1) for i in range(ls+1)]
for ss in range(ls):
    for st in range(lt):
        table[ss+1][st+1] = table[ss][st] + 1 if s[ss] == t[st] else max(table[ss+1][st], table[ss][st+1] )

ans = ""
ss, st = ls, lt
while ss * st != 0:
    if table[ss][st] == table[ss-1][st]:
        ss -= 1
    elif table[ss][st] == table[ss][st-1]:
        st -= 1

    else:
        ss -= 1
        st -= 1
        ans = s[ss] + ans

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

T, P = input(), input()
for i in range(len(T)):
	if T[i:].startswith(P):
		print(i)

### FIXED CODE ###

T, P = input(), input()
T_len = len(T)
P_len = len(P)
for i in range(T_len - P_len + 1):
	if T[i:i + P_len] == P:
		print(i)
### BUGGY CODE ###

#encoding:utf-8

import numpy as np

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

memory = {}

def count_answer(x,y):
    count = 0
    actions = {0:[-1,0],1:[0,1],2:[1,0],3:[0,-1]}
    # print("x,y:",x,y)
    for action0 in range(4):
        next_x = x + actions[action0][0]
        next_y = y + actions[action0][1]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1:
            pass
        elif next_x >= H or next_y >= W:
            pass
        elif [next_x,next_y] in reach_position:
            pass
        elif S_[next_x,next_y] == ".":
            reach_position.append([next_x,next_y])
            for action in range(4):
                next_next_x = next_x +actions[action][0]
                next_next_y = next_y +actions[action][1]
                # print(next_next_x,next_next_y)
                if next_next_x == -1 or next_next_y == -1:
                    pass
                elif next_next_x >= H or next_next_y >= W:
                    pass
                elif S_[next_next_x,next_next_y] == "#":

                    memory_key = str(next_next_x)+str(next_next_y)
                    if memory_key in memory.keys():
                        tem_poss = memory[memory_key]
                    else:
                        tem_poss = count_answer(next_next_x,next_next_y)
                    for tem_pos in tem_poss:
                        if tem_pos in reach_position:
                            pass
                        else:
                            reach_position.append(tem_pos)
    memory[str(x)+str(y)] = reach_position
    # memory[[x,y]] = reach_position
    return reach_position

answer = 0
for i in range(H):
    for j in range(W):
        if S_[i,j] == "#":
            reach_position = []
            reach_position = count_answer(i,j)
            answer += len(reach_position)
print(answer)


### FIXED CODE ###

#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)


def count_answer(x,y,num_b,num_w):
    # print(used)

    if S[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S[next_x][next_y] != S[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S[i][j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)
### BUGGY CODE ###

from collections import Counter
import math


def nCr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

ac = dict(Counter(a))

ans = 0
for k, v in ac.items():
    if v < 2:
        ac[k] = (v, 0)
    else:
        c = nCr(v, 2)
        ac[k] = (v, c)
        ans += c

for i in a:
    v = ac[i]
    if v[0] - 1 < 2:
        print(ans - v[1])
    else:
        print(ans - v[1] + nCr(v[0] - 1, 2))

### FIXED CODE ###

from collections import Counter
from operator import mul
from functools import reduce


def nCr(n, r):
    r = min(n - r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under


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

ac = dict(Counter(a))

ans = 0
for k, v in ac.items():
    if v < 2:
        ac[k] = (v, 0, 0)
    else:
        c = nCr(v, 2)
        ans += c
        if v - 1 < 2:
            ac[k] = (v, c, 0)
        else:
            ac[k] = (v, c, nCr(v - 1, 2))

for i in a:
    v = ac[i]
    if v[0] - 1 < 2:
        print(ans - v[1])
    else:
        print(ans - v[1] + v[2])
### BUGGY CODE ###

n,k=map(int,input().split())
arr=list(map(int,input().split()))
brr=list(map(lambda x: max(x,0),arr))
total=0
for i in range(n-k+1):
    total=max(total,sum(brr[:i])+max(0,sum(arr[i:i+k]))+sum(brr[i+k:]))
print(total)


### FIXED CODE ###

n,k=map(int,input().split())
arr=list(map(int,input().split()))
brr=list(map(lambda x: max(x,0),arr))
crr=[0]
cum=0
for b in brr[:(n-k)]:
    cum+=b
    crr.append(cum)
drr=[0]
cum=0
for b in list(reversed(brr))[:(n-k)]:
    cum+=b
    drr.append(cum)
drr.reverse()
K=sum(arr[:k])
krr=[]
for i in range(n-k):
    krr.append(max(0,K))
    K-=arr[i]
    K+=arr[i+k]
krr.append(max(0,K))

ans=0
for i in range(n-k+1):
    ans=max(ans,crr[i]+drr[i]+krr[i])
print(ans)
### BUGGY CODE ###

N = int(input())
an = list(map(int, input().split()))
ans = 10e+9
for i in range(1, N):
    ans = min(ans, abs(sum(an[:i]) - sum(an[i:])))
print(ans)


### FIXED CODE ###

from itertools import accumulate
N = int(input())
an = list(map(int, input().split()))
res = [0] + an
res = list(accumulate(res))
ans = 10e+9
for i in range(1, N):
    ans = min(ans, abs(res[i] - (res[-1]-res[i])))
print(ans)