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

def comb(n,k,p):
  from math import factorial
  
  if n / 2 < k:
    k = n - k
  
  if n<0 or k<0 or n<k: 
    return 0
  if n==0 or k==0: 
    return 1
  
  a=factorial(n) %p
  b=factorial(k) %p
  c=factorial(n-k) %p
  return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p

def power_func(a,b,p):
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p))%p

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


count = 0
i = n - 1
j = k - 1
k = 0
while True:
  tmp = comb(i, j, 10**9+7)
  count += tmp * a[-1-k]
  count -= tmp * a[k]
  count = count % (10 ** 9 + 7)
  if i == j:
    break
  i -= 1
  k += 1
    
print(count)

### FIXED CODE ###

# x^n % mod
def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def main():
  MOD = 10 ** 9 + 7
  n,k = map(int,input().split())
  a = sorted(list(map(int,input().split())))
  
  g_k = 1
  for i in range(1,k):
    g_k *= i
    g_k %= MOD
    
  gyakugen = pow_k(g_k,MOD-2,MOD)
  array = [0] * (n+1)
  array[k-1] = g_k
  
  for i in range(k, n+1):
    array[i] = array[i-1] * i * pow_k(i-k+1,MOD-2,MOD)
    array[i] %= MOD
    
  ans = 0
  for i in range(n):
    if i-k+1 >= 0:        
      ans += array[i] * gyakugen * a[i]
      
    if n-i-k >= 0:
      ans -= array[n-i-1] * gyakugen * a[i]
      
    ans %= MOD
      
  print(ans)

main()
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def calc():
  n=int(input())
  arr=list(map(int,input().split()))
  l=int(input())
  pos=0
  dbl=[[0]*(n+1)]
  for i in range(n):
    for j in range(pos,n):
      if arr[j]-arr[i]>l:
        dbl[0][i+1]=j
        pos=j
        break
    else:
      dbl[0][i+1]=n
  for _ in range(16):
    tmp=[0]*(n+1)
    for i in range(n+1):
      tmp[i]=dbl[-1][dbl[-1][i]]
    dbl.append(tmp)
  q=int(input())
  for _ in range(q):
    a,b=map(int,input().split())
    if a>b:
      a,b=b,a
    l=0
    r=b-a+1
    while r-l!=1:
      mid=(l+r)//2
      tmp=a
      for i in range(17):
        if mid&(1<<i):
          tmp=dbl[i][tmp]
      if tmp>=b:
        r=mid
      else:
        l=mid
    print(r)
calc()

### FIXED CODE ###

import bisect
import sys
input=sys.stdin.readline

def calc():
  n=int(input())
  arr=list(map(int,input().split()))
  l=int(input())
  pos=0
  dbl=[[0]*(n+1)]
  for i in range(n):
      dbl[0][i+1]=bisect.bisect_right(arr,arr[i]+l)
  for _ in range(n.bit_length()-1):
    tmp=[0]*(n+1)
    for i in range(n+1):
      tmp[i]=dbl[-1][dbl[-1][i]]
    dbl.append(tmp)
  q=int(input())
  for _ in range(q):
    a,b=map(int,input().split())
    if a>b:
      a,b=b,a
    l=0
    r=b-a+1
    while r-l!=1:
      mid=(l+r)//2
      tmp=a
      for i in range(mid.bit_length()):
        if mid&(1<<i):
          tmp=dbl[i][tmp]
      if tmp>=b:
        r=mid
      else:
        l=mid
    print(r)
calc()
### BUGGY CODE ###

K,S = [int(i) for i in input().rstrip().split()]

X=Y=Z=K+1

rec = 0
for i in range(X):
  for j in range(Y):
    for k in range(Z):
      xyz = i + j + k			#合計値
      if xyz == S:
        rec += 1

print(rec)

### FIXED CODE ###

K,S = [int(i) for i in input().rstrip().split()]

lst_temp = [ int(i) for i in range(K + 1)]

recCnt = 0
for x in lst_temp:
  for y in lst_temp:
    z = S - x - y 
    if z >= 0 and z <= K:
      recCnt += 1
      
print(recCnt)
### BUGGY CODE ###

N,D,A = map(int,input().split())
X = []
for _ in range(N):
    x,h = map(int,input().split())
    X.append([x,h])
X.sort()
ans = 0
for i in range(N):
    x = X[i][0]
    h = X[i][1]
    if h % A == 0:
        count = h // A
    else:
        count = h // A + 1
    ans += count
    dmg = A * count
    #print(ans,dmg)
    for j in range(i+1,N):
        if  x + (2 * D) < X[j][0]:
            break
        else:
            X[j][1] = max(0,X[j][1]-dmg)
            #print(X[j])
print(ans)

### FIXED CODE ###

N,D,A = map(int,input().split())
X = []
for _ in range(N):
    x,h = map(int,input().split())
    X.append([x,h])
X.sort()
if X[-1][0] - X[0][0] < 2 * D:
    ans = 0 
    max = 0
    for i in range(N):
        if X[i][1] > max:
            max = X[i][1]
    if max % A == 0:
        ans = max // A
    else:
        ans = max // A + 1
else:
    ans = 0
    for i in range(N):
        h = int(X[i][1])
        if h != 0:
            x = int(X[i][0])
            if h % A == 0:
                count = h // A
            else:
                count = h // A + 1
            ans += count
            dmg = A * count
    #print(ans,dmg)
            for j in range(i+1,N):
                x2 = int(X[j][0])
                h2 = int(X[j][1])
                if  x + (2 * D) < x2:
                    break
                else:
                    X[j][1] = max(0,h2-dmg)
                    #print(X[j])
print(ans)
### BUGGY CODE ###

import sys

import numpy as np


def calc_mul4_dp(n, aaa):
    dp = np.array([list(range(16))] * (n + 1), dtype=np.int64)

    next_a = aaa[-1]
    for i in range(n - 2, -1, -1):
        a = aaa[i]
        if a > next_a:
            cnt = 0  # a[i]以上になるためにa[i+1]に4をかけなければならない最小回数
            b = next_a
            while a > b:
                b <<= 2
                cnt += 1
            print('a > na', cnt, file=sys.stderr)
            dp[i, :-cnt] += dp[i + 1, cnt:]
            dp[i, -cnt:] += dp[i + 1, -1] + np.arange(1, cnt + 1) * (n - i - 1)
        else:
            cnt = 0  # a[i]に4をかけても次に影響が出ない最大回数
            b = a
            while next_a >= b:
                b <<= 2
                cnt += 1
            cnt -= 1
            print('a < na', cnt, file=sys.stderr)
            dp[i, :cnt] += dp[i + 1, 0]
            dp[i, cnt:] += dp[i + 1, :16 - cnt]
        next_a = a
    print(dp, file=sys.stderr)
    return dp


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    mul4dp = (fdp.T[0] + bdp.T[0]) * 2
    print(mul4dp, file=sys.stderr)
    return (mul4dp + np.arange(n + 1)).min()


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))


### FIXED CODE ###

import numpy as np


def calc_mul4_dp(n, aaa):
    # dp[i] = aaa[i] 以右をascendingにするために4をかける必要のある回数

    # 「支配的」である数と位置を記録するstack
    # 支配的: それを4倍すると、それより右で次に支配的な数までは全て4倍する必要のある数
    # (支配的な数, ←をいじらなかった場合の支配区間の最後の数, 最初の数の位置)
    stack = [(10 ** 20, 10 ** 20, n), (aaa[-1], aaa[-1], n - 1)]
    INF = 10 ** 19
    result = [0, 0]

    for i in range(n - 2, -1, -1):
        a = aaa[i]
        c = a
        inc = 0
        while (c << 2) > stack[-1][0]:
            b, e, j = stack.pop()
            mul = 0
            while c > b:
                b <<= 2
                mul += 1
            inc += mul * (stack[-1][2] - j)
            c = min(e << (2 * mul), INF)
        stack.append((a, c, i))
        result.append(inc)
        # print(a, stack, result)
    result = np.add.accumulate(result, dtype=np.int64)[::-1]
    return result


def solve(n, aaa):
    fdp = calc_mul4_dp(n, aaa)
    bdp = calc_mul4_dp(n, aaa[::-1])[::-1]
    # print(fdp)
    # print(bdp)
    return ((fdp + bdp) * 2 + np.arange(n + 1, dtype=np.int64)).min()


def test():
    import random
    n = 200000
    # aaa = random.choices(range(1, 10 ** 9), k=n)
    # aaa = [1, 10 ** 9] * (n // 2)
    aaa = list(range(10 ** 9, 10 ** 9 - n, -1))
    print(n)
    # print(aaa)
    print(solve(n, aaa))


# test()

n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(key=lambda x: -x)
b.sort(key=lambda x: -x)
c.sort(key=lambda x: -x)

xy = []
xyz = []
m = min(3000, x*y*z)


for ia in a:
    for ib in b:
        xy.append(ia+ib)
xy.sort(key=lambda x: -x)
xy = xy[:m]

for ix in xy:
    for ic in c:
        xyz.append(ix+ic)


ans = sorted(xyz, key=lambda x: -x)
ans = ans[:k]

for a in ans:
    print(a)


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

xyz = []

for ia in range(len(a)):
    for ib in range(len(b)):
        for ic in range(len(c)):
            if (ia+1)*(ib+1)*(ic+1) <= k:
                xyz.append(a[ia]+b[ib]+c[ic])
            else:
                break

xyz.sort(reverse=True)
for l in xyz[:k]:
    print(l)
### BUGGY CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    while True:
        k = -1
        for i in range(1,N+1):
            if not visited[i]:
                k = i
                break
        if k == -1:break
        dfs(k)



    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for tree in stack.keys():
        for k in range(1,N+1):
            tr = belong[k]
            candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline
from collections import defaultdict
sys.setrecursionlimit(10**7)
def run():

    N,M,K = map(int,sysread().split())
    to = [[] for _ in range(N+1)]
    n_to = [0 for _ in range(N + 1)]
    for i in range(1,M+1):
        a,b = map(int, sysread().split())
        #a,b = AB[i]
        to[a].append(b)
        n_to[a] += 1
        to[b].append(a)
        n_to[b] += 1

    stack = defaultdict(lambda:0)
    visited = [False] * (N+1)
    belong = [None] * (N+1)


    def dfs(n):
        _stack = [n]
        visited[n] = True
        while _stack:
            node = _stack.pop()
            stack[n] += 1
            belong[node] = n
            for next in to[node]:
                if not visited[next]:
                    _stack.append(next)
                    visited[next] = True
        return None


    for i in range(1,N+1):
        if not visited[i]:
            dfs(i)

    block = [0 for _ in range(N+1)]
    for i in range(1, K+1):
        c,d = map(int, sysread().split())
        #c, d = CD[i]
        if belong[c] == belong[d]:
            block[c] += 1
            block[d] += 1

    candidates = [0] * (N+1)

    for k in range(1,N+1):
        tr = belong[k]
        candidates[k] = stack[tr] - 1 - n_to[k] - block[k]

    print(' '.join(map(str, candidates[1:])))

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

a, b, c = map(int, input().split())
ans = 0

if a == b == c and a%2==0:
    ans = -1
else:
    for i in range(10**9):
        if a%2==1 or b%2==1 or c%2==1:
            if a%2==1 and b%2==1 and c%2==1:
                pass
            else:
                break
        x = a
        y = b
        z = c
        a = y//2 + z//2
        b = x//2 + z//2 
        c = x//2 + y//2
        ans +=1

print(ans)


### FIXED CODE ###

a, b, c = map(int, input().split())
ans = 0

if a == b == c and a%2==0:
    ans = -1
else:
    for i in range(10**9):
        if a%2==1 or b%2==1 or c%2==1:
            break
        x = a
        y = b
        z = c
        a = y//2 + z//2
        b = x//2 + z//2 
        c = x//2 + y//2
        ans +=1

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

S=list(input())
M=S.count("?")
N=len(S)
A=[0]*(N+1)
Q=[0]*(N+1)
AB=[0]*(N+1)
AQandQB=[0]*(N+1)
QQ=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  Q[i]=Q[i-1]
  if S[i-1] is "A":
    A[i]+=1
  elif S[i-1] is "?":
    Q[i]+=1
  AB[i]=AB[i-1]
  AQandQB[i]=AQandQB[i-1]
  QQ[i]=QQ[i-1]
  if S[i-1] is "B":
    AB[i]+=A[i-1]
    AQandQB[i]+=Q[i-1]
  elif S[i-1] is "?":
    AQandQB[i]+=A[i-1]
    QQ[i]+=Q[i-1]
  ABC[i-1]=ABC[i-1]%(10**9+7)
  ABC[i]=ABC[i-1]
  if S[i-1] is "C":
    ABC[i]+=AB[i-1]*(3**M)+(AQandQB[i-1])*(3**(M-1))+QQ[i-1]*(3**(M-2))
  elif S[i-1] is "?":
    ABC[i]+=AB[i-1]*(3**(M-1))+(AQandQB[i-1])*(3**(M-2))+QQ[i-1]*(3**(M-3))
print(int(ABC[N]%(10**9+7)))

### FIXED CODE ###

S=input()
N=len(S)
O=1
A=[0]*(N+1)
AB=[0]*(N+1)
ABC=[0]*(N+1)
for i in range(1,N+1):
  A[i]=A[i-1]
  AB[i]=AB[i-1]
  ABC[i]=ABC[i-1]
  if S[i-1] is "A":
    A[i]+=O
  elif S[i-1] is "B":
    AB[i]+=A[i-1]
  elif S[i-1] is "C":
    ABC[i]+=AB[i-1]
  elif S[i-1] is "?":
    A[i]*=3
    A[i]+=O
    AB[i]*=3
    AB[i]+=A[i-1]
    ABC[i]*=3
    ABC[i]+=AB[i-1]
    O*=3
  A[i]=A[i]%(10**9+7)
  AB[i]=AB[i]%(10**9+7)
  ABC[i]=ABC[i]%(10**9+7)
  O=O%(10**9+7)
print(int(ABC[N]%(10**9+7)))
### BUGGY CODE ###

n = int(input())
ans = []
for _ in range(n):
    s = input()
    if s  not in ans:
        ans.append(s)
print(len(ans))

### FIXED CODE ###

n = int(input())
ans = []
for _ in range(n):
    ans.append(input())
ans = set(ans)
print(len(ans))
### BUGGY CODE ###

from sys import stdin
 
inf = 10**9 + 1

def solve():
    n = int(stdin.readline())
    R = [int(stdin.readline()) for i in range(n)]

    ans = max_profit2(n, R)

    print(ans)

def max_profit(n, R):
    max_d = -inf
    min_v = R[0]

    for i in range(1, n):
        max_d = max(max_d, R[i] - min_v)
        min_v = min(min_v, R[i])

    return max_d

def max_profit2(n, R):
    max_dif = -inf

    for left in range(n):
        for j in range(left + 1, n):
            max_dif = max(max_dif, R[j] - R[left])

    return max_dif
    
def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None
 
if __name__ == '__main__':
    solve()

### FIXED CODE ###

from sys import stdin
 
inf = 10**9 + 1

def solve():
    n = int(stdin.readline())
    max_d = -inf
    min_v = inf * 2

    for i in range(n):
        r = int(stdin.readline())

        max_d = max(max_d, r - min_v)
        min_v = min(min_v, r)

    print(max_d)


def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf') for i in range(N)] for j in range(N)]
    for a, b, c in ABC:
        dist[a-1][b-1] = dist[b-1][a-1] = c
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = dist[i][j] if dist[i][j] < dist[i][k] + dist[k][j] else dist[i][k] + dist[k][j]

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i] - 1
            b = r[i+1] - 1
            move += dist[a][b]
        ans = ans if ans < move else move

    print(ans)

main()


### FIXED CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * (N + 1) for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
        dist[a][a] = dist[b][b] = 0
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()
### BUGGY CODE ###

import math
N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

for i in range(M):
  A[-1] = A[-1] //2
  A = sorted(A)
  
print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
Ai = list(map(lambda x: x*(-1), A))
heapq.heapify(Ai)

for i in range(M):
  maxA = heapq.heappop(Ai)*(-1)
  waribiki = maxA // 2
  heapq.heappush(Ai,waribiki * (-1))
  #print(Ai)
  
print(sum(Ai) * (-1))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(200000000)

N, M, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
max_num = 0

def dfs(curr_a, curr_b, choice, time_required, count):
    global max_num
    if choice == 0:
        if curr_a >= N - 1:
            if max_num < count:
                max_num = count
            return
        else:
            curr_a += 1
            time_required += a[curr_a]
    else:
        if curr_b >= M - 1:
            if max_num < count:
                max_num = count
            return
        else:
            curr_b += 1
            time_required += b[curr_b]
    if time_required > K:
        return
    count += 1
    if max_num < count:
        max_num = count
    dfs(curr_a, curr_b, 0, time_required, count)
    dfs(curr_a, curr_b, 1, time_required, count)


if sum(a) + sum(b) <= K:
    print(N + M)
else:
    curr_a = -1
    curr_b = -1
    time_required = 0
    count = 0
    dfs(curr_a, curr_b, 0, time_required, count)
    curr_a = -1
    curr_b = -1
    time_required = 0
    count = 0
    dfs(curr_a, curr_b, 1, time_required, count)
    print(max_num)


### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N + 1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
ans = 0

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+A[i-1][0]+A[i-1][1]+A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+A[i-1][0]+A[i-1][1]-A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+A[i-1][0]-A[i-1][1]+A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+A[i-1][0]-A[i-1][1]-A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-A[i-1][0]+A[i-1][1]+A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-A[i-1][0]+A[i-1][1]-A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-A[i-1][0]-A[i-1][1]+A[i-1][2])
ans = max(ans, dp[n][m])

dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-A[i-1][0]-A[i-1][1]-A[i-1][2])
ans = max(ans, dp[n][m])

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(n)]
ans = 0

for i in range(8):
    value_list = []
    for a in A:
        value_list.append((2*(i&1)-1)*a[0] + (2*((i>>1)&1)-1)*a[1] + (2*((i>>2)&1)-1)*a[2])
    value_list.sort(reverse=True)
    ans = max(ans, sum(value_list[:m]))

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

N, M = map(int, input().split())
LRC = [list(map(int, input().split())) for _ in range(M)]
INF = 10 ** 10
graph = [[INF] * (N+1) for _ in range(N+1)]
for i in range(N+1):
    graph[i][i] = 0
LRC.sort(key=lambda x: x[2], reverse=True)
LRC.sort()
dp = [INF] * (N+1) # dp[0]は使わない
visited = 1
dp[1] = 0
for l, r, c in LRC:
    if l > visited:
        print(-1)
        exit()
    if r > visited:
        visited = r
    x = dp[l] + c
    for i in range(l, r+1):
        dp[i] = min(dp[i], x)
if dp[N] == INF:
    print(-1)
else:
    print(dp[N])


### FIXED CODE ###

import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def dijkstra(start):
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for cost, next in graph[prev]:
            d1 = d + cost
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

N, M = lr()
INF = 10 ** 15
graph = [[] for _ in range(N+1)] # 1-indexed
for i in range(2, N+1):
    graph[i].append((0, i-1))

for _ in range(M):
    l, r, c = lr()
    graph[l].append((c, r))

dist = dijkstra(1)

if dist[N] == INF:
    print(-1)
else:
    print(dist[N])
# 19
### BUGGY CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
xli = na()
li = []
ans = 1000000000
idx = -1
for i in range(n):
    if xli[i] > 0:
        idx = i
        break
if idx == -1:
    print(abs(xli[-k]))
elif idx == 0:
    print(abs(xli[k-1]))
else:
    for i in range(max(idx - k, 0), min(idx+1, n-k+1)):
        t = xli[i:i + k]
        if t[0] * t[-1] < 0:
            ans = min(ans, 2 * abs(t[0]) + abs(t[-1]), abs(t[0]) + 2 * abs(t[-1]))
        else:
            if t[0] <= 0:
                ans = min(ans, abs(t[0]))
            else:
                ans = min(ans, abs(t[-1]))
    print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, k = na()
xli = na()
li = []
ans = 1000000000
idx = -1
for i in range(n):
    if xli[i] > 0:
        idx = i
        break
if idx == -1:
    print(abs(xli[-k]))
elif idx == 0:
    print(abs(xli[k-1]))
else:
    for i in range(max(idx - k, 0), min(idx+1, n-k+1)):
        if xli[i] * xli[i + k -1] < 0:
            ans = min(ans, 2 * abs(xli[i]) + xli[i + k -1], abs(xli[i]) + 2 * xli[i + k -1])
        else:
            if xli[i + k -1] <= 0:
                ans = min(ans, abs(xli[i]))
            else:
                ans = min(ans, abs(xli[i + k -1]))
    print(ans)
### BUGGY CODE ###

import numpy as np

a = int(input())
p = list(map(int,input().split()))
mod = 10**9 + 7

sum_list =[p[i]*p[t] for i in range(a) for t in range(a) if i<=t and not i ==t]
num = np.sum(sum_list)
num = num%mod
print(num)

### FIXED CODE ###

import itertools as itr

a = int(input())
p = list(map(int,input().split()))
mod = 10**9 + 7
ans =0
sum_list = list(itr.accumulate(p))
for i in range(len(p)-1):
    o = p[i+1]
    w =sum_list[i]
    ans = (ans+o*w%mod)%mod
print(ans)