Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#C
n = int(input())
h = list(map(int,input().split()))
tmp = 0
prev = True
result = [0 for _ in range(n)]

for i in range(n-1):
    if prev:
        for j in range(i,n-1):
            if h[j] >= h[j+1]:
                tmp += 1
            else:
                break
    if tmp > 0:
        prev = False
    else:
        prev = True
        
    result[i] = tmp
    tmp = 0
    
print(max(result))
            

Fixed submission:
#C
n = int(input())
h = list(map(int,input().split()))

a,b = 0,0

for i in range(n-1):
    if h[i] >= h[i+1]:
        a += 1
        b = max(b,a)
    else:
        a = 0
        
print(b)

Buggy python submission (verdict: Time Limit Exceeded):
#C
n = int(input())
h = list(map(int,input().split()))
tmp = 0
result = [0 for _ in range(n)]
for i in range(n-1):
    for j in range(i,n-1):
        if h[j] >= h[j+1]:
            tmp += 1
        else:
            break
            
    result[i] = tmp
    tmp = 0
    
print(max(result))

Fixed submission:
#C
n = int(input())
h = list(map(int,input().split()))

a,b = 0,0

for i in range(n-1):
    if h[i] >= h[i+1]:
        a += 1
        b = max(b,a)
    else:
        a = 0
        
print(b)
Buggy python submission (verdict: Runtime Error):
#E
from collections import deque
import bisecit
n = int(input())
a = [int(input()) for _ in range(n)]
result = deque()

for i in a:
    idx = bisect.bisect_left(result,i)
    if idx == 0:
        result.appendleft(i)
        
    else:
        result[idx-1] = i
        
print(len(result))

Fixed submission:
#E
from collections import deque
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
result = deque()

for i in a:
    idx = bisect.bisect_left(result,i)
    if idx == 0:
        result.appendleft(i)
        
    else:
        result[idx-1] = i
        
print(len(result))

Buggy python submission (verdict: Time Limit Exceeded):
#E
import heapq
n = int(input())
a = [int(input()) for _ in range(n)]
b = a[:]
heapq.heapify(b)


cnt = 0

while len(a)>0:
    a_l = a.pop(0)
    for i in range(len(a)-1,-1,-1):
        if a[i] > a_l:
            a_r = a.pop(i)
            break
    for j in range(len(a)-1,-1,-1):
        if a_l < a[j] < a_r:
            a_r = a.pop(j)
            
    cnt += 1

print(cnt)

Fixed submission:
#E
from collections import deque
import bisect
n = int(input())
a = [int(input()) for _ in range(n)]
result = deque()

for i in a:
    idx = bisect.bisect_left(result,i)
    if idx == 0:
        result.appendleft(i)
        
    else:
        result[idx-1] = i
        
print(len(result))
Buggy python submission (verdict: Runtime Error):
#D
#https://tech-kyopro.com/atcoder-abc126-d
n = int(input())
edges = [list(map(int,input().split())) for _ in range(n-1)]
#頂点iと隣接する頂点とその距離を格納[["隣接する頂点","その距離"]]
a = [[] for _ in range(n+1)]

for i in edges:
    a[i[0]].append([i[1],i[2]])
    a[i[1]].append([i[0],i[2]])
    
#頂点1からの距離をdepth
depth = [-1 for _ in range(n+1)]
depth[0] = 0

def dfs(a,s):
    for v in a[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(a,v[0])
            
dfs(a,1)

for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)


Fixed submission:
#D
#https://tech-kyopro.com/atcoder-abc126-d

import sys
sys.setrecursionlimit(500*500)
n = int(input())
edges = [list(map(int,input().split())) for _ in range(n-1)]
#頂点iと隣接する頂点とその距離を格納[["隣接する頂点","その距離"]]
a = [[] for _ in range(n+1)]

for i in edges:
    a[i[0]].append([i[1],i[2]])
    a[i[1]].append([i[0],i[2]])
    
#頂点1からの距離をdepth
depth = [-1 for _ in range(n+1)]
depth[0] = 0

def dfs(a,s):
    for v in a[s]:
        if depth[v[0]] == -1:
            depth[v[0]] = depth[s] + v[1]
            dfs(a,v[0])
            
dfs(a,1)

for d in depth[1:]:
    if d % 2 == 0:
        print(0)
    else:
        print(1)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
import bisect
a.sort()

idx = bisect.bisect_left(a, 0)
sm = [abs(x) for x in a]
if idx % 2 == 0:
    print(sum(sm))
else:
    print(sum(sm) - 2*min(abs(a[idx]), abs(a[idx-1])))

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
import bisect
a.sort()

idx = bisect.bisect_left(a, 0)
sm = [abs(x) for x in a]
if idx % 2 == 0:
    print(sum(sm))
else:
    print(sum(sm) - 2*min(sm))

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int,input().split()))
import bisect
a.sort()

idx = bisect.bisect_left(a, 0)

if idx % 2 == 0:
    print(sum(abs(a)))
else:
    sm = [abs(x) for x in a]
    print(sum(sm) - 2*min(abs(a[idx]), abs(a[idx-1])))

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
import bisect
a.sort()

idx = bisect.bisect_left(a, 0)
sm = [abs(x) for x in a]
if idx % 2 == 0:
    print(sum(sm))
else:
    print(sum(sm) - 2*min(sm))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
x = list(map(int,input().split()))

x_sort = sorted(x[:])

for i in range(n):
    x_sort_temp = x_sort[:]
    x_sort_temp.remove(x[i])
    #print("x_sort_removed",x_sort_temp)
    print(x_sort_temp[(n-1)//2])

Fixed submission:
n = int(input())
x = list(map(int,input().split()))

x_sort = sorted(x[:])
a,b = x_sort[n//2 - 1], x_sort[n//2]

for i in range(n):
    if x[i] <= a:
        print(b)
    else:
        print(a)
Buggy python submission (verdict: Time Limit Exceeded):
#ABC-79-B
from functools import lru_cache

n = int(input())

#@lru_cache(maxsize=None)
def lucas(n):
    if n == 1:
        return 2
    elif n == 2:
        return 1
    else:
        return lucas(n-2)+lucas(n-1)
    

print(lucas(n+1))
    

Fixed submission:
#ABC-79-B
from functools import lru_cache

n = int(input())

@lru_cache(maxsize=None)
def lucas(n):
    if n == 1:
        return 2
    elif n == 2:
        return 1
    else:
        return lucas(n-2)+lucas(n-1)
    

print(lucas(n+1))
Buggy python submission (verdict: Time Limit Exceeded):
#ABC073-C
n = int(input())
paper = []
for _ in range(n):
    a = int(input())
    if a in set(paper):
        paper.remove(a)
    else:
        paper.append(a)

print(len(paper))
    

Fixed submission:
#ABC073-C
from collections import Counter
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
  
cnt = 0
c = Counter(a)
for i in c.values():
    if i % 2 == 0:
        continue
    else:
        cnt += 1
        
print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
#ABC073-C
n = int(input())
paper = []
for _ in range(n):
    a = int(input())
    if a in set(paper):
        paper.remove(a)
    else:
        paper.append(a)

print(len(paper))
    

Fixed submission:
#ABC073-C
from collections import Counter
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
  
cnt = 0
c = Counter(a)
for i in c.values():
    if i % 2 == 0:
        continue
    else:
        cnt += 1
        
print(cnt)
Buggy python submission (verdict: Runtime Error):
#AGC016-A
from collections import Counter 
s = input()
alphabet = "abcdefghijklmnopqrstuvwxyz"
cnt = 0
result = []
for i in alphabet:
    s_tmp = s 
    cnt = 0
    for k in range(len(s_tmp)):
        s_new= ""
        for j in range(len(s_tmp)-1):
            if s_tmp[j] == i or s_tmp[j+1] == i:
                s_new += i
            else:
                s_new += s_tmp[j]
        cnt += 1
        s_tmp = s_new
        if len(set(s_new)) == 1:
            result.append(cnt)
            break
            
 

#print(result)
print(min(result))



Fixed submission:
#AGC016-A
from collections import Counter 
s = input()
alphabet = "abcdefghijklmnopqrstuvwxyz"

result = []
if len(set(s)) == 1:
    result.append(0)
for i in alphabet:
    s_tmp = s 
    cnt = 0
    for k in range(len(s_tmp)):
        s_new= ""
        for j in range(len(s_tmp)-1):
            if s_tmp[j] == i or s_tmp[j+1] == i:
                s_new += i
            else:
                s_new += s_tmp[j]
        cnt += 1
        if len(set(s_new)) == 1:
            result.append(cnt)
            break        

        s_tmp = s_new
        
            
 

#print(result)
print(min(result))
Buggy python submission (verdict: Runtime Error):
n, a, b = list(map(int, input().split()))
k = b - a
if k % 2 == 1:
    print(min(a-1, n-b)+1+(z-1)//2)
else:
    print(z//2)


Fixed submission:
n, a, b = list(map(int, input().split()))
k = b - a
if k % 2 == 1:
    print(min(a-1, n-b)+1+(k-1)//2)
else:
    print(k//2)
Buggy python submission (verdict: Runtime Error):
a, b = int(input()), int(input())
if a <= 8 and b <= 8:
    print("Yay!")
else:
    print(":(")


Fixed submission:
a, b = map(int, input().split())
if a <= 8 and b <= 8:
    print("Yay!")
else:
    print(":(")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
b = list(set(a))

comb = 0
for i in range(len(b)):
  num = a.count(b[i])
  comb += num*(num-1)//2

[print(comb-a.count(a[i])+1) for i in range(len(a))]

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
b = [0]*(n+1)
cnt = 0

for i in range(n):
    b[a[i]] += 1
for i in range(1,n+1):
    cnt += b[i]*(b[i]-1)//2
for i in range(n):
    if(b[a[i]]>1):
        print(cnt - b[a[i]]*(b[a[i]]-1)//2 + (b[a[i]]-1)*(b[a[i]]-2)//2)
    else:
        print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

s = input()
q = INT()
p = [input() for i in range(q)]
flag = 0

for i in range(q):
        if int(p[i][0]) == 1:
                flag = 1 - flag
        else:
                t, f, c = p[i].split()
                if int(f) == 1:
                        if flag == 0:
                                s = c + s
                        else:
                                s = s + c
                else:
                        if flag == 0:
                                s = s + c
                        else:
                                s = c + s 
print(s if flag == 0 else s[::-1])

Fixed submission:
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

s = input()
q = INT()
p = [0]*q
flag = 0
c0 = c1 = ''

for i in range(q):
        p[i] = input()
        if p[i][0] == '1':
                flag = 1 - flag
        else:
                t, f, c = p[i].split()
                if (f == '1' and flag == 0) or (f == '2' and flag == 1):
                        c0 = c + c0
                else:
                        c1 = c1 + c

s = c0 + s + c1
print(s if flag == 0 else s[::-1])

Buggy python submission (verdict: Time Limit Exceeded):
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

s = input()
q = INT()
p = [input() for i in range(q)]

for i in range(q):
        if int(p[i][0]) == 1:
                s = s[::-1]
        else:
                t, f, c = p[i].split()
                if int(f) == 1:
                        s = c + s
                else:
                        s = s + c 
print(s)

Fixed submission:
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

s = input()
q = INT()
p = [0]*q
flag = 0
c0 = c1 = ''

for i in range(q):
        p[i] = input()
        if p[i][0] == '1':
                flag = 1 - flag
        else:
                t, f, c = p[i].split()
                if (f == '1' and flag == 0) or (f == '2' and flag == 1):
                        c0 = c + c0
                else:
                        c1 = c1 + c

s = c0 + s + c1
print(s if flag == 0 else s[::-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))

max_reg = 0
for i in range(n - k + 1):
  max_reg = max(max_reg, (sum(p[i:i+k])+k)/2)
  
print(max_reg)

Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))

sum_reg = (sum(p[0:k])+k)/2
max_reg = sum_reg
for i in range(k, n):
  sum_reg = sum_reg + (p[i]-p[i-k])/2
  max_reg = max(max_reg, sum_reg)
  
print(max_reg)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))

max_reg = 0
for i in range(n - k + 1):
  max_reg = max(max_reg, (sum(p[i:i+k])+k)/2)
  
print(max_reg)

Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))

sum_reg = (sum(p[0:k])+k)/2
max_reg = sum_reg
for i in range(k, n):
  sum_reg = sum_reg + (p[i]-p[i-k])/2
  max_reg = max(max_reg, sum_reg)
  
print(max_reg)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
p = list(map(int, input().split()))
q = []

for x in p:
  q.append((x+1)/2)
  
max_reg = 0
for i in range(n - k + 1):
  max_reg = max(max_reg, sum(q[i:i+k]))
  
print(max_reg)

Fixed submission:
n, k = map(int, input().split())
p = list(map(int, input().split()))

sum_reg = (sum(p[0:k])+k)/2
max_reg = sum_reg
for i in range(k, n):
  sum_reg = sum_reg + (p[i]-p[i-k])/2
  max_reg = max(max_reg, sum_reg)
  
print(max_reg)
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil,floor,comb,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, n = MAP()
a = [0]*n
b = [0]*n
dp = [inf]*(h+1)
dp[0] = 0
# dp[j]: ダメージ>=jとするために必要な魔力の最小値

for i in range(n):
    a[i], b[i] = MAP()

for i in range(n):
    for j in range(0,h+1):
        if j < a[i]:
            dp[j] = min(dp[j], b[i])
        else:
            dp[j] = min(dp[j], dp[j-a[i]]+b[i])

print(dp[h])

Fixed submission:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

h, n = MAP()
a = [0]*n
b = [0]*n
dp = [inf]*(h+1)
dp[0] = 0
# dp[j]: ダメージ>=jとするために必要な魔力の最小値

for i in range(n):
    a[i], b[i] = MAP()

for i in range(n):
    for j in range(0,h+1):
        if j < a[i]:
            dp[j] = min(dp[j], b[i])
        else:
            dp[j] = min(dp[j], dp[j-a[i]]+b[i])

print(dp[h])
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

def is_ok(arg):
    return l[arg] < l[i] + l[j]

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

n = INT()
l = sorted(LIST())

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += meguru_bisect(n, j) - j
print(ans)

Fixed submission:
from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
l = sorted(LIST())

ans = 0
for i in range(n-2):
    right = i + 2
    for j in range(i+1, n-1):
        left = j + 1
        while right < n-1 and l[right] < l[i] + l[j]:
            right += 1
        ans += right - left
        if l[right] < l[i] + l[j]:
            ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import bisect,copy,heapq,itertools,string
from collections import *
from math import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, a, b, c, d = MAP()
s = input()

flag = 0
for i in range(min(a,b)+1,max(c,d)):
        if (a < i < c or b < i < d) and s[i] == s[i-1] == '#':
                print("No")
                exit()       
        elif max(a,b) <= i <= min(c,d) and s[i-1] == s[i] == s[i+1] == '.':
                flag = 1

if c > d and flag == 0:
        print("No")
else:
        print("Yes")

Fixed submission:
import bisect,copy,heapq,itertools,string
from collections import *
from math import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, a, b, c, d = MAP()
s = 'a' + input()

flag = 0
for i in range(min(a,b)+1,max(c,d)):
        if (a < i < c or b < i < d) and s[i] == s[i-1] == '#':
                print("No")
                exit()       
        elif max(a,b) <= i <= min(c,d) and s[i-1] == s[i] == s[i+1] == '.':
                flag = 1

if c > d and flag == 0:
        print("No")
else:
        print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
s = input()
count = 0
flag = 1
que = deque([0]*(2*k+1))
ans = 0
for x in s:
    if x == '0':
        if flag == 1:
            que.append(count)
            que.popleft()
            ans = max(ans, sum(que)) 
            count = 0
        flag = 0
        count += 1
    else:
        if flag == 0:
            que.append(count)
            que.popleft()
            count = 0
        flag = 1
        count += 1

que.append(count)
que.popleft()
if s[-1] == '0':
    que.popleft()
ans = max(ans,sum(que))
print(ans)

Fixed submission:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
s = input()
count = 0
flag = 1
que = deque([0]*(2*k+1))
ans = 0
tmp = 0
for x in s:
    if x == '0':
        if flag == 1:
            que.append(count)
            tmp += count - que.popleft()
            ans = max(ans, tmp) 
            count = 0
        flag = 0
        count += 1
    else:
        if flag == 0:
            que.append(count)         
            tmp += count - que.popleft()
            count = 0
        flag = 1
        count += 1

que.append(count)
tmp += count - que.popleft()
if s[-1] == '0':
    tmp -= que.popleft()
ans = max(ans,sum(que))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect,collections,copy,heapq,itertools,math,string
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
x = sorted(LIST())
ans = math.inf
v = [0]*n

if n >= m:
    print(0)
    exit()

for v[1:n] in itertools.combinations(range(1,m),n-1):
    tmp = 0
    for i in range(n):
        if(i<n-1):
            tmp += x[v[i+1]-1]-x[v[i]]
        else:
            tmp += x[m-1]-x[v[i]]
    ans = min(ans, tmp)
print(ans)

Fixed submission:
import bisect,collections,copy,heapq,itertools,math,string
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
x = sorted(LIST())
dx = [x[i+1]-x[i] for i in range(m-1)]
dx.sort(reverse=True)

if n >= m:
    print(0)
else:
    print(x[m-1]-x[0]-sum(dx[0:n-1]))