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

n,k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]

INF = int(pow(10, 10))

a = [INF] * n
a[0] = 0

for i in range(1, n):
	for j in range(1, k+1):
		if i-j >= 0:
			b = a[i-j] + abs(h[i-j]-h[i])
			if b < a[i]:
				a[i] = b

print(a[n-1])

### FIXED CODE ###

n,k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]

INF = int(pow(10, 10))

a = [INF] * n
a[0] = 0

for i in range(1, n):
	for j in range(1, k+1):
		if i-j >= 0:
			b = a[i-j] + abs(h[i-j]-h[i])
			if b < a[i]:
				a[i] = b

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

import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)


for i in range(n-1):
    for j in range(i+2, n):
        if j < x or i > y:
            dist = j-i
        else:
            dist = min([j - i, abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 
final[0] = n
res = [str(one) for one in final]
print ("\n".join(res))

### FIXED CODE ###

import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)


for i in range(n-1):
    for j in range(i+2, n):
        if j < x or i > y:
            dist = j-i
        else:
            dist = min([j - i, abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 
final[0] = n
res = [str(one) for one in final]
print ("\n".join(res))
### BUGGY CODE ###

n,m = map(int,input().split())
displace = []
for _ in range(m):
    displace.append(int(input()))

dp = [1]
if 1 in displace:
    dp.append(0)
else:
    dp.append(1)

for i in range(2,n+1):
    next_case = 0
    if i not in displace:
        next_case += dp[i-1]+dp[i-2]
    dp.append(next_case%1000000007)
print(dp[-1])

### FIXED CODE ###

n,m = map(int,input().split())
displace = {}
for _ in range(m):
    displace[int(input())] = 1
dp = {0:1}
if 1 in displace:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2,n+1):
    next_case = 0
    if i not in displace:
        next_case += dp[i-1]+dp[i-2]
    dp[i] = next_case%1000000007
print(dp[n])
### BUGGY CODE ###

from heapq import heapify, heappush, heappop
def greenandredapples():
    X, Y, A, B, C = list(map(int, input().split()))
    RedD = sorted(list(map(int, input().split())))
    GreenD = sorted(list(map(int, input().split())))
    Colorl = sorted(list(map(int, input().split())))

    considered = RedD[-X:] + GreenD[-Y:]
    #print(considered)
    replacements = len(Colorl)
    #print(Colorl)
    while replacements >= 0 and len(Colorl) > 0:
        heapify(considered)
        smallest = heappop(considered)
        #print("ffff", smallest)
        r = Colorl.pop(0)
        #print("gggg", r, Colorl)
        if smallest < r:
            heappush(considered, r)
        else:
            heappush(considered, smallest)
        #print("ccc", considered)
        replacements -= 1
    #print(considered)
    return sum(considered)
print(greenandredapples())

### FIXED CODE ###

def greenandredapples():
    X, Y, A, B, C = list(map(int, input().split()))
    RedD = sorted(list(map(int, input().split())))
    GreenD = sorted(list(map(int, input().split())))
    Colorl = sorted(list(map(int, input().split())))

    considered = RedD[-X:] + GreenD[-Y:]
    Colorl.extend(considered)
    return sum(sorted(Colorl,reverse=True)[:X+Y])

print(greenandredapples())
### BUGGY CODE ###

# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    import itertools
    pattern = list(itertools.combinations_with_replacement(range(1, m+1), n))

    maxp = 0
    for x in pattern:
        get = 0
        for array in arrays:
            
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]
        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

import numpy as np
arrays = list(np.array_split(aa, q))

solve(n, m, q, arrays)


### FIXED CODE ###

# coding: utf-8
# Your code here!

def solve(n, m, q, arrays):
    from itertools import combinations_with_replacement
    pattern = list(combinations_with_replacement(range(1, m+1), n))

    maxp = 0
    for x in pattern:
        get = 0
        for array in arrays:
            if x[array[1]-1] - x[array[0]-1] == array[2]:
                get += array[3]

        maxp = max(maxp, get)

    print(maxp)

n, m, q, *aa = map(int, open(0).read().split())

arrays = []
loop = 0
array = []
for x in aa:
    array.append(x)
    loop += 1
    if loop % 4 == 0:
        arrays.append(array)
        array = []

solve(n, m, q, arrays)
### BUGGY CODE ###

n = int(input())

a = [0] * n

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

sum = 1

for i in a:
    sum *= i

if (sum > 1000000000000000000):
    print(-1)
else:
    print(sum)


### FIXED CODE ###

n = int(input())

a = [0] * n

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

sum = 1
cnt = 0
if 0 in a:
    print(0)
else:
    for i in a:
        sum *= i
        if sum > 1000000000000000000:
            print(-1)
            cnt = 1
            break
    if cnt == 0:
        print(sum)
### BUGGY CODE ###

N, Y = map(int, input().split())
x = 0
y = 0
z = 0

if Y/1000 - N < 0:
    print(-1,-1,-1)

else:
    for x in range(0, int(Y - 1000 * N / 9000)+ 1):
        y = (Y - 1000 * N - 9000 * x) / 4000
        if y == int(y)  and y >= 0:
            y = int(y)
            z = N - x - y
            if 0 <= z <= N:
                print(x, y, z)
                break
                
    if x == int(Y - 1000 * N / 9000):
        print(-1,-1,-1)

### FIXED CODE ###

N, Y = map(int, input().split())
x,y,z = 0,0,0
for x in range(0, N + 1):
    for y in range(0, N - x +1):
        z = N - x - y
        if 10000 * x + 5000 * y + 1000 * z == Y:
            break
    if 10000 * x + 5000 * y + 1000 * z == Y :
        break

if 10000 * x + 5000 * y + 1000 * z == Y :
    print(x,y,z)
else:
    print(-1,-1,-1)
### BUGGY CODE ###

n = int(input())

l = [i for i in range(n)]

print(sum(l))


### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

#!/usr/bin/env python3

n=int(input())  #->n=5
ai=list(map(int,input().split()))  #->nl=[1,2,-,n]

temp = 0
for i in range(n-1):
    for j in range(i+1,n):
        temp = temp + ai[i]*ai[j]

temp = temp % (10**9+7)
print(temp)



### FIXED CODE ###

#!/usr/bin/env python3

n=int(input())  #->n=5
a=list(map(int,input().split()))  #->nl=[1,2,-,n]
mod=int(1e9+7)

# Accumulate
pre=[0]*n
pre[0]=a[0]
for i in range(1,n):  pre[i]=pre[i-1]+a[i]
ans=0
for i in range(1,n):  ans=(ans+(a[i-1]*(pre[n-1]-pre[i-1]))%mod)%mod
print(ans)
### BUGGY CODE ###

N,P = map(int,input().split())
S = input()
d = {}

ans = 0
for i in range(len(S),-1,-1):
  r = 0
  for j in range(i):
    x = int(S[i-1-j])*(10**j)
    #print(x)
    if x not in d:
      d[x] = x%P
    r += d[x]
    r %= P
    if r == 0:
      ans += 1
print(ans)


### FIXED CODE ###

def main():
  N,P = map(int,input().split())
  S = input()

  ans = 0
  if P == 2 or P == 5:
    for i in range(N):
      if int(S[i])%P == 0:
        ans += i+1
  else:
    # r = [0] * (N+1)
    # for i in range(N):
    #   r[N-1-i] = int(S[N-1-i:])%P
    # for i in range(N):
    #   for j in range(i,N):
    #     if (r[i]-r[j+1])%P == 0:
    #       ans += 1
    d = {}
    r = 0
    for i in range(N):
      r = (r+int(S[N-1-i])*pow(10,i,P))%P
      if r in d:
        d[r] += 1
      else:
        d[r] = 1
    if 0 in d:
      d[0] += 1
    for k,v in d.items():
      ans += v*(v-1)//2
  
  print(ans)

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

from collections import deque
N,M=map(int,input().split())
if M==0:
    print("Yes")
    quit()
G=[[] for i in range(N)]
for i in range(M):
    l,r,d=map(int,input().split())
    G[l-1].append((l-1,r-1,d))
    G[r-1].append((r-1,l-1,-d))
x=["a"]*N
y=[1]*N
z=[[0]*N for i in range(N)]
stack=deque()
for i in range(N):
    if y[i]:
        stack.extend(G[i])
        y[i]=0
    if len(stack)==0:
        continue
    while(stack):
        l,r,d=stack.popleft()
        if x[l]=="a":
            x[l]=0
        if x[r]=="a":
            x[r]=x[l]+d
            continue
        if x[r]!=x[l]+d:
            print("No")
            quit()
        y[r]=0
        z[l][r]=1
        z[r][l]=1
        for l1,r1,d1 in G[r]:
            if z[l1][r1] or z[r1][l1]:
                continue
            stack.append((l1,r1,d1))
if max(x)-min(x)>10**9:
    print("No")
else:
    print("Yes")


### FIXED CODE ###

#重み付きUnion-Find

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        wei[x] += wei[par[x]]
        par[x] = px
        return px

#xの根から距離
def weight(x):
    find(x)
    return wei[x]


#w[y]=w[x]+wとなるようにxとyを併合
def unite(x,y,w):
    w += wei[x]-wei[y]
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
            w = -w
        par[x] += par[y]
        par[y] = x
        wei[y] = w
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#x,yが同じ集合に属するときのwei[y]-wei[x]
def diff(x,y):
    return weight(y)-weight(x)

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

#初期化
#par:根なら-size,子なら親の頂点
#wei:親からの距離,根なら0
par = [-1]*n
wei = [0]*n

for i in range(m):
    l,r,d = map(int,input().split())
    l,r = l-1,r-1
    if same(l,r):
        if d != diff(l,r):
            print('No')
            exit()
    else:
        unite(l,r,d)
print('Yes')
### BUGGY CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
for i in range(n):
    print(max(A[: i] + A[i + 1:]))

### FIXED CODE ###

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

high = sorted(A, reverse=True)[: 2]

for i in range(n):
    if A[i] == high[0]:
        ans = high[1]
    else:
        ans = high[0]
    print(ans)
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]

max_cnt = 0
for i in range(N+1):
    a = A[:i]
    if sum(a) > K:
        continue
    for j in range(M+1):
        b = B[:j]
        if sum(b) > K:
            continue
        total = sum(a) + sum(b)
        if total <= K:
            cnt = len(a) + len(b)
            max_cnt = max(max_cnt, cnt)

print(max_cnt)

### FIXED CODE ###

from itertools import accumulate

N, M, K = map(int, input().split())
A = list(accumulate(int(i) for i in input().split()))
B = list(accumulate(int(i) for i in input().split()))

a,b = [0],[0]
for ai in A:
    a.append(ai)
for bj in B:
    b.append(bj)

cnt = 0
best0 = M
for i in range(N+1):
   ai = a[i]
   for j in range(best0, -1, -1):
       bj = b[j]
       if ai + bj <= K:
           cnt = max(cnt, i + j)
           best0 = j
           break

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

N = int(input())
S = input()

def zal(s):
    i = 1
    j = 0
    _N = len(s)
    Z = [0]*_N
    Z[0] = _N
    while i < _N:
        while i + j < _N and s[j] == s[i+j]:
            j += 1
        Z[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < _N and k + Z[k] < j:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

res = 0
for i in range(N):
    _S = S[i:]
    Z = zal(_S)
    for j in range(len(Z)):
        if Z[j] <= j:
            res = max(res, Z[j])
print(res)


### FIXED CODE ###

N = int(input())
S = input()
 
def zal(s):
    i = 1
    j = 0
    _N = len(s)
    Z = [0]*_N
    Z[0] = _N
    res = 0
    while i < _N:
        while i + j < _N and s[j] == s[i+j]:
            j += 1
        Z[i] = j
 
        if Z[i] <= i:
            res = max(res, Z[i])
 
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < _N and k + Z[k] < j:
            Z[i+k] = Z[k]
 
            if Z[i+k] <= i+k:
                res = max(res, Z[i+k])
 
            k += 1
        i += k
        j -= k
    return res
 
ans = 0
for i in range(N):
    _S = S[i:]
    res = zal(_S)
    ans = max(ans, res)
print(ans)
### BUGGY CODE ###

S = list(input())
Q = int(input())
for i in range(Q):
    a, *b = input().split()
    if a == "1":
        S = S[::-1]
    elif a == "2":
        c, d = b
        if c == "1":
            S.insert(0, d)
        elif c == "2":
            S.append(d)
print(*S, sep="")

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
x = 1
l=[]
for i in range(Q):
    a, *b = input().split()
    if a == "1":
        x *= -1
    elif a == "2":
        c, d = b
        if (c == "2" and x == -1) or  (c == "1" and x == 1):
            S.appendleft(d)
        else:
            S.append(d)
if x == -1:
    S.reverse()
print(*S, sep="")
### BUGGY CODE ###

from collections import deque

H,W = map(int,input().split())
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]

def bfs(l):
    q = deque(l)
    for l_ in l:
        check[l_[0]][l_[1]] = 0
    while q:
        y,x = q.popleft()
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny,nx = y+dy,x+dx
            if 0 <= ny < H and 0<= nx < W:
                if check[ny][nx] == -1 and A[ny][nx] == '.':
                    check[ny][nx] = check[y][x] + 1
                    q.append([ny,nx])

L = []
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            L.append([h,w])
bfs(L)
ans = 0
for c in check:
    ans = max(ans,max(c))
print(ans)

### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]

def bfs(l):
    ans = 0
    q = deque(l)
    for l_ in l:
        check[l_[0]][l_[1]] = 0
    while q:
        y,x = q.popleft()
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny,nx = y+dy,x+dx
            if 0 <= ny < H and 0<= nx < W:
                if check[ny][nx] == -1 and A[ny][nx] == '.':
                    check[ny][nx] = check[y][x] + 1
                    ans = max(ans,check[ny][nx])
                    q.append([ny,nx])
    return ans 

L = []
for h,a in enumerate(A):
    for w,a_ in enumerate(a):
        if a_ == '#':
            L.append([h,w])
print(bfs(L))
### BUGGY CODE ###

# import io
# import sys

# _INPUT = """\
# 1 4 120
# 100 1 1 1 1 1 1 1 1 1 1
# 80 10 10 10 10
# """
# sys.stdin = io.StringIO(_INPUT)

####################################################################
import sys
def p(*_a):
  return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################

N,M,K = map(int, input().split())
A = [0] + [int(i) for i in input().split()]
B = [0] + [int(i) for i in input().split()]


# 累積和
from itertools import accumulate
C = list(accumulate(A))
D = list(accumulate(B))

p(*C)
p(*D)

ans = 0

for i, c in enumerate(C):
  for j, d in enumerate(D):
    p(i,j,c,d)
    if c + d > K: break
    ans = max(ans, i+j)

print(ans)


### FIXED CODE ###

# import io
# import sys

# _INPUT = """\
# 1 4 120
# 100 1 1 1 1 1 1 1 1 1 1
# 80 10 10 10 10
# """
# sys.stdin = io.StringIO(_INPUT)

####################################################################
import sys
def p(*_a):
  return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################

N,M,K = map(int, input().split())
A = [0] + [int(i) for i in input().split()]
B = [0] + [int(i) for i in input().split()]


# 累積和
from itertools import accumulate
C = list(accumulate(A))
D = list(accumulate(B))

p(*C)
p(*D)

ans = 0
d = len(D) - 1
for c in range(len(C)):
  if C[c] > K: break
  while True:
    if C[c] + D[d] <= K: break
    d -= 1

  ans = max(ans , c + d)

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

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
readline = sys.stdin.readline
a = [int(i) for i in readline().split()]
#bc = [[int(i) for i in readline().split()] for _ in range(m)]

import heapq

heapq.heapify(a)

for i in range(m):
#    b = bc[i][0]; c = bc[i][1]
    b,c = [int(i) for i in readline().split()]
    for _ in range(b):
        if a[0] < c:
            _ = heapq.heappop(a)
            heapq.heappush(a, c)
        else:
            break
    
ans = sum(a)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
readline = sys.stdin.readline
A = [int(i) for i in readline().split()]

A.sort()

CB = []
for _ in range(m):
    b, c = [int(i) for i in readline().split()]
    CB.append([c, b])
    
CB.sort(reverse=True)

idx = 0
c = 0
for i in range(n):
    if A[i] < CB[idx][0]:
        A[i] = CB[idx][0]
        c += 1
    if CB[idx][1] <= c:
        idx += 1
        c = 0
    if idx >= m:
        break

print(sum(A))
### BUGGY CODE ###

import collections
N=int(input())
A=[int(s) for s in input().split(" ")]

for i in range(1,N+1):
    count=A.count(i)
    print(count)

### FIXED CODE ###

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

List = [0] * (n)
for i in range(n-1):
    List[A[i]-1] += 1

for i in List:
    print(i)
### BUGGY CODE ###

H,W,D = [int(n) for n in raw_input().split(" ")]
Location = {}
for h in range(1,H + 1):
	A = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A):
		Location[a] = (h, w+1)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for q in range(1,Q+1):
	l, r = L[q], R[q]
	C[l,l] = 0
	C[r,r] = 0
	cur_dist = 0
	for x1 in range(l, r, D):
		x2 = x1 + D
		if (x1, r) in C:
			C[(l,r)] = C[l, x1] + C[(x1,r)]
			break
		elif (x1,x2) not in C:
			h1, w1 = Location[x1]
			h2, w2 = Location[x2]
			C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + C[(x1,x2)]
		C[(l,x2)] = cur_dist
	print C[(l,r)]


### FIXED CODE ###

H,W,D = [int(n) for n in raw_input().split(" ")]
Location = {}
for h in range(1,H + 1):
	A = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A):
		Location[a] = (h, w+1)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for d in range(1,D+1):
	C[d,d] = 0
	cur_dist = 0
	for x1 in range(d, H * W + 1, D):
		x2 = x1 + D
		if x2 > H * W: 
			break
		h1, w1 = Location[x1]
		h2, w2 = Location[x2]
		#C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + abs(h1 - h2) + abs(w1 - w2)
		C[(d,x2)] = cur_dist
	
for q in range(1,Q+1):
	l, r = L[q], R[q]
	d = l % D
	if d == 0: 
		d = D
	print (C[(d,r)] - C[(d,l)])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def recursive(i,j):
  if i>j:
    return 0
  elif dp.get((i,j)):
    return dp[(i,j)]
  dp[(i,j)]=max(nums[i]-recursive(i+1,j),nums[j]-recursive(i,j-1))
  return dp[(i,j)]

dp={}
n=int(input())
nums=list(map(int,input().split()))
#print(dp)
print(recursive(0,n-1))



### FIXED CODE ###

dp={}
n=int(input())
nums=list(map(int,input().split()))
#print(dp)
#print(recursive(0,n-1))
dp=[[0]*(n+1) for _ in range(n+1)]
for i in range(n-1,-1,-1):
    for j in range(i,n,1):
        dp[i][j]=max(nums[i]-dp[i+1][j],nums[j]-dp[i][j-1])
print(dp[0][n-1])
### BUGGY CODE ###

mod = 10**9+7
S = input()

dp = [[0] * 13 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    s = S[len(S)-i-1]
    if s == '?':
        c = range(10)
    else:
        c = [int(s)]

    for d in c:
        for j in range(13):
            dp[i+1][(j+d*10**i) % 13] += dp[i][j]

    # for k in range(13):
    #     dp[i+1][k] = dp[i+1][k] % mod

    # print(dp)

print(dp[len(S)][5] % mod)


### FIXED CODE ###

mod = 10**9+7
S = [int(x) if x != "?" else -1 for x in input()]

dp = [[0] * 13 for i in range(len(S)+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] == -1:
        for d in range(10):
            for j in range(13):
                dp[i+1][(j*10+d) % 13] += dp[i][j]
    else:
        d = S[i]
        for j in range(13):
            dp[i+1][(j*10+d) % 13] += dp[i][j]

    for k in range(13):
        dp[i+1][k] = dp[i+1][k] % mod

    # print(dp)

print(dp[len(S)][5])
### BUGGY CODE ###

with open(0) as f:
    N, *a = map(int, f.read().split())
F = [x for x in a[:N]] #Fの要素は加えるか取り除くかの2択
C = [x for x in a[N:2*N]] 
B = [-x for x in a[2*N:]] #Bの要素は引くか取り除くかの二択
import heapq as hq
hq.heapify(F)
hq.heapify(B)

#Cを二分し、前半はFと、後半はBとで演算を行う
#演算方法(c in C)
#前半：cがF[0]より大きければF[0]を取り除くN個の一つとし、cをスコアに加える
#後半：-cがB[0]より大きければB[0]を取り除くN個の一つとし、cをスコアから引く
#どちらも場合も条件を満たさない場合はそのｃを取り除くN個の一つとする
#計算量：O(N*N*logN)
#途中計算をメモして計算量軽減
from copy import deepcopy
memoF = [[]] * (N+1) #C[:i]を前半としたときのFとの演算結果
memoF[0] = deepcopy(F)
memoB = [[]] * (N+1) #C[i:]を後半としたときのBとの演算結果
memoB[N] = deepcopy(B)
for i in range(N):
    if C[i] > F[0]:
        hq.heapreplace(F, C[i])
    if -C[N-1-i] > B[0]:
        hq.heapreplace(B, -C[N-1-i])
    memoF[i+1] = deepcopy(F)
    memoB[N-1-i] = deepcopy(B)

Scores = [sum(memoF[i])+sum(memoB[i]) for i in range(N+1)]
ans = max(Scores)
print(ans)

### FIXED CODE ###

with open(0) as f:
    N, *a = map(int, f.read().split())
F = [x for x in a[:N]] #Fの要素は加えるか取り除くかの2択
C = [x for x in a[N:2*N]] 
B = [-x for x in a[2*N:]] #Bの要素は引くか取り除くかの二択
import heapq as hq
#ヒープにして常に最小値を追跡
hq.heapify(F)
hq.heapify(B)

#Cを二分し、前半はFと、後半はBとで演算を行う
#演算方法(c in C)
#前半：cがF[0]より大きければF[0]を取り除くN個の一つとし、cをスコアに加える
#後半：-cがB[0]より大きければB[0]を取り除くN個の一つとし、cをスコアから引く
#どちらも場合も条件を満たさない場合はそのｃを取り除くN個の一つとする
#計算量：O(N*N*logN)
#途中計算をメモして計算量軽減
from copy import deepcopy
memoF = [0] * (N+1) #C[:i]を前半としたときのFとの演算結果の要素和
memoF[0] = sum(F)
memoB = [0] * (N+1) #C[i:]を後半としたときのBとの演算結果の要素和
memoB[N] = sum(B)
for i in range(N):
    if C[i] > F[0]:
        memoF[i+1] = memoF[i] + C[i] - hq.heapreplace(F, C[i])
    else:
        memoF[i+1] = memoF[i]

    if -C[N-1-i] > B[0]:
        memoB[N-1-i] = memoB[N-i] - C[N-1-i] - hq.heapreplace(B, -C[N-1-i])
    else:
        memoB[N-1-i] = memoB[N-i]

Scores = [memoF[i]+memoB[i] for i in range(N+1)]
ans = max(Scores)
print(ans)
### BUGGY CODE ###

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

ans=0
for i in range(n):
    for j in range(i+1,n):
        ans = ans%(10**9+7) + (a[i]*a[j])%(10**9+7)
print(ans%(10**9+7))


### FIXED CODE ###

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

a2=[a[n-1]]
for i in range(n-1,0,-1):
    a2.append(a2[-1]+a[i-1])
ans=0
for i in range(n-1):
    ans = ( ans + (a[i]*a2[-i-2]) )%(10**9+7)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
nums=[x+1 for x in range(n)]
cnt=0
ans=0
for i in nums:
  cnt=0
  for t in l:
    if(t[0]<=i<=t[1]):
      cnt+=1
  if(cnt==len(l)):
    ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
nums=[x+1 for x in range(n)]
ans=0
r=[0,100000]
for i in l:
  r[0]=max(r[0],i[0])
  r[1]=min(r[1],i[1])
for i in nums:
  if(r[0]<=i<=r[1]):
    ans+=1
print(ans)
### BUGGY CODE ###


N=int(input())
for n in range(1,N+1):
    ans=0
    for x in range(1,101):
        tx=x**2
        if tx>n :
            break
        for y in range(1,101-x):
            ty=tx+y**2+x*y
            if ty>n :
                break
            if (x+y)**2-4*(ty-n)<0:
                break
            s=((x+y)**2-4*(ty-n))**0.5
            if s.is_integer():
                z=-1*(x+y)+s
                if z>0:
                    ans+=1
    print(ans)

### FIXED CODE ###


N=int(input())
for n in range(1,N+1):
    ans=0
    for x in range(1,101):
        tx=x**2
        if tx>n-2*x :
            break
        for y in range(x,101-x):
            ty=tx+y**2+x*y
            if ty>n-x-y :
                break
            ss=(x+y)**2-4*(ty-n)
            if ss<0:
                break
            s=ss**0.5
            if s.is_integer():
                z=int((-1*(x+y)+s)/2)
                if z>=y:
                    
                    if len(set([x,y,z]))==1:
                        ans+=1
                    if len(set([x,y,z]))==2:
                        ans+=3
                    if len(set([x,y,z]))==3:
                        ans+=6
    print(ans)