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

#dojkstra (prioroty queue ver.)
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

for i in range(V):
    G.append([])
for i in range(E):
    at,bt,ct=map(int,input().strip().split(' '))
    G[at-1].append([ct,bt-1])
    G[bt-1].append([ct,at-1]) #無向グラフのときはon
'''
#入力が0-indexedのとき
    G[at].append([ct,bt])
    G[bt].append([ct,at]) #無向グラフのときはon
'''
#入力が1-indexedのとき

#lisの置換を全て作る
import math
def n_perm(lis):
    permed=[]
    ind=[i for i in range(len(lis))]
    for j in range(math.factorial(len(lis))):
        for i in range(len(ind)-2,-1,-1):
            if ind[i]<ind[i+1]:
                k=i
                break
        for i in range(len(ind)-1,k,-1):
            if ind[k]<ind[i]:
                l=i
                break
        ind[k], ind[l]=ind[l], ind[k]
        a=ind[k+1:]
        a.reverse()
        ind=ind[:k+1]+a
        permed.append([lis[i] for i in ind])
    return permed

def dijkstra(s):
    d=[inf]*V
    d[s]=0
    q=queue.PriorityQueue()
    q.put([0,s])
    while q.empty()==False:
        dq,v=q.get()
        if d[v]<dq:
            continue
        for i in range(len(G[v])):
            ec, et=G[v][i]
            #print(ec,et)
            if d[et]>d[v]+ec:
                d[et]=d[v]+ec
                q.put([d[et],et])
    return d

dist=[]
for i in range(V):
    dist.append(dijkstra(i))

rperm=n_perm(rlis)

ans=inf
for i in range(math.factorial(R)):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[i][j]-1][rperm[i][j+1]-1]
    ans=min(ans,a_tmp)
    
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

#dojkstra
import itertools
import queue
G=[]
#infの値に注意
inf=3*10**15
V, E, R=map(int,input().strip().split(' '))
rlis=list(map(int,input().strip().split(' ')))

cost=[[inf]*V for i in range(V)]
for i in range(E):
    fr, to, co=map(int,input().strip().split(' '))
    cost[fr-1][to-1]=co
    cost[to-1][fr-1]=co
def dijkstra(s):
    d=[inf]*V
    used=[False]*V
    d[s]=0
    while True:
        v=-1
        for u in range(V):
            if used[u]==False and(v==-1 or d[u]<d[v]):
                v=u
        if v==-1:
            break
        used[v]=True
        for u in range(V):
            d[u]=min(d[u],d[v]+cost[v][u])
    return d

dist=[None] * V
for i in rlis:
    dist[i-1]=dijkstra(i-1)

ans=inf
for rperm in itertools.permutations(rlis):
    a_tmp=0
    for j in range(R-1):
        a_tmp+=dist[rperm[j]-1][rperm[j+1]-1]
    ans=min(ans,a_tmp)

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

# coding: utf-8
# Your code here!
s=input()
t=input()

dp=[[[0,0,0] for j in range(len(t)+1)] for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            if dp[i][j][0]+1>dp[i+1][j+1][0]:
                    dp[i+1][j+1]=[dp[i][j][0]+1,i,j]
        else:
            if dp[i][j][0]>dp[i+1][j][0]:
                dp[i+1][j]=[dp[i][j][0],i,j]
            if dp[i][j][0]>dp[i][j+1][0]:
                dp[i][j+1]=[dp[i][j][0],i,j]

temp_max=-1
start=[len(dp)-1,-1]
for index,item in enumerate(dp[-1]):
    if item[0]>temp_max:
        temp_max=item[0]
        start[1]=index
        
ans=[]
while start!=[0,0]:
    temp=dp[start[0]][start[1]][1:]
    if start[0]-temp[0]==1 and start[1]-temp[1]==1:
        ans.append(s[temp[0]])
    start=temp[:]


print("".join(ans[::-1]))



### FIXED CODE ###

# coding: utf-8
# Your code here!
s=list(input())
t=list(input())

dp=[[0]*(len(t)+1) for i in range(len(s)+1)]

for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1]==t[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])
            
#print(dp)

ans=""
ns=len(s)
nt=len(t)

while ns>0 and nt>0:
    #print(ns,nt,ans)
    if s[ns-1]==t[nt-1]:
        ans+=s[ns-1]
        ns-=1
        nt-=1
    elif dp[ns][nt]==dp[ns-1][nt]:
        ns-=1
    else:
        nt-=1
        
print(ans[::-1])
### BUGGY CODE ###

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

for i in range(n):
    nums[i] -= (i + 1)
    
x = min(nums)
y = max(nums)
z = []
for i in range(x, y+1):
    c = 0
    for j in range(n):
        c += abs(nums[j] - i)
    else:
        z.append(c)

print(min(z))

### FIXED CODE ###

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

for i in range(n):
    nums[i] -= (i + 1)

nums.sort()
        
if (n-1) % 2 != 0:
    m = n//2 - 1
else:
    m = (n-1)//2
    
a = sum(nums[m+1:]) - (n-m-1)*nums[m]
b = - sum(nums[0:m+1]) + (m+1)*nums[m]

print(a+b)
### BUGGY CODE ###

s = input()
t = input()
def lcs(s,t):
    m = len(s)
    n = len(t)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            x = s[i-1]
            y = t[j-1]
            if x == y:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = dp[i-1][j]
                if dp[i][j] < dp[i][j-1]:
                    dp[i][j] = dp[i][j-1]
    res = ""
    while n > 0 and m > 0:
        if dp[m][n] == dp[m-1][n]:
            m -= 1
        elif dp[m][n] == dp[m][n-1]:
            n -= 1
        else:
            n -= 1
            m -= 1
            res = s[m] + res
    print(res)
    return 0
a = lcs(s,t)

### FIXED CODE ###

s = input()
t = input()
m = len(s)
n = len(t)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        x = s[i-1]
        y = t[j-1]
        if x == y:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = dp[i-1][j]
            if dp[i][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
res = ""
while n != 0 and m != 0:
    if dp[m][n] == dp[m-1][n]:
        m -= 1
    elif dp[m][n] == dp[m][n-1]:
        n -= 1
    else:
        n -= 1
        m -= 1
        res = s[m] + res
print(res)
### BUGGY CODE ###

import math

def readInt():
	return int(input())
 
def readInts():
	return list(map(int, input().split()))
 
def readChars():
	return input().split()

N,Y = readInts()
o = Y



for x in range(Y//10000,-1,-1):
	o=Y-x*10000
	#print(Y,x,o)
	for y in range(o//5000,-1,-1):
		#print(y)
		o=Y-x*10000-y*5000
		for z in range(o//1000,-1,-1):
			if x+y+z>N:
				break
			res = x*10000+y*5000+z*1000
			if res==Y and sum([x,y,z])==N:
				print(str(x)+" "+str(y)+" "+str(z))
				exit()

print("-1 -1 -1")

### FIXED CODE ###

import math

def readInt():
	return int(input())
 
def readInts():
	return list(map(int, input().split()))
 
def readChars():
	return input().split()

N,Y = readInts()
o = Y



for x in range(Y//10000,-1,-1):
	o=Y-x*10000
	#print(Y,x,o)
	for y in range(o//5000,-1,-1):
		#print(y)
		o=Y-x*10000-y*5000
		z=o//1000
		res = x*10000+y*5000+z*1000
		if x+y+z>N or res>Y:
			break
		if res==Y and x+y+z==N:
			print(str(x)+" "+str(y)+" "+str(z))
			exit()

print("-1 -1 -1")
### BUGGY CODE ###

import itertools
n,a,b,c=map(int,input().split())
l=[int(input()) for i in range(n)]
ll=[i for i in range(1,n+1)]
x=[]
for i in range(1,n+1):
    z=list(itertools.combinations(l,i))
    zz=list(itertools.combinations(ll,i))
    for j in range(len(z)):
        x.append([sum(z[j]),(i-1)*10,list(zz[j])])
x.sort()
#print(x)
A=[];B=[];C=[]
for i in range(len(x)):
    A.append([x[i][1]+abs(a-x[i][0]),x[i][2]])
    B.append([x[i][1]+abs(b-x[i][0]),x[i][2]])
    C.append([x[i][1]+abs(c-x[i][0]),x[i][2]])
#A.sort();B.sort();C.sort()
m=len(A)
ans=float('inf')
for i in range(m):
    for j in range(m):
        for k in range(m):
            if len(A[i][1]+B[j][1]+C[k][1])!=len((set(A[i][1]+B[j][1]+C[k][1]))):
                continue
            else:
                #print(A[i][1]+B[j][1]+C[k][1])
                ans=min(ans,A[i][0]+B[j][0]+C[k][0])
print(ans)    
    

### FIXED CODE ###

import itertools
n,a,b,c=map(int,input().split())
l=[int(input()) for i in range(n)]
l.sort()
ll=[i for i in range(1,n+1)]
x=[]
for i in range(1,n+1):
    z=list(itertools.combinations(l,i))
    zz=list(itertools.combinations(ll,i))
    for j in range(len(z)):
        x.append([sum(z[j]),(i-1)*10,list(zz[j])])
x.sort()
#print(x)
A=[];B=[];C=[]
for i in range(len(x)):
    A.append([x[i][1]+abs(a-x[i][0]),x[i][2]])
    B.append([x[i][1]+abs(b-x[i][0]),x[i][2]])
    C.append([x[i][1]+abs(c-x[i][0]),x[i][2]])
A.sort();B.sort();C.sort()
#print(A)
#print(B)
#print(C)
m=len(A)
ans=float('inf')
for i in range(m):
    for j in range(m):
        for k in range(m):
            if len(A[i][1]+B[j][1]+C[k][1])>=9:
                break
            elif len(A[i][1]+B[j][1]+C[k][1])==len((set(A[i][1]+B[j][1]+C[k][1]))):
                ans=min(ans,A[i][0]+B[j][0]+C[k][0])
print(ans)
### BUGGY CODE ###

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


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def gcda(a):
    ret = a[0]
    for i in range(1, len(a)):
        ret = gcd(ret, a[i])
    return ret


ans = 1
for i in range(N):
    a = A[:i] + A[i+1:]
    ans = max(ans, gcda(a))

print(ans)

### FIXED CODE ###

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


def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a % b)


L = [0] * (N + 1)
R = [0] * (N + 1)
for i in range(N):
    L[i+1] = gcd(L[i], A[i])

for i in range(N-1, -1, -1):
    R[i] = gcd(R[i+1], A[i])

ans = 1
for i in range(N):
    ans = max(ans, gcd(L[i], R[i+1]))

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

# -*- coding: utf-8 -*-
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

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


g_max = 1
for i in range(n):
    d = a_l.pop(0)

    if n-1==1:
        g = a_l[0]
    else:
        g = gcd(a_l[0], a_l[1])
        if n-1!=2:
            for j in range(2,n-1):
                g=gcd(g,a_l[j])
    # print(g)
    g_max = max(g, g_max)
    # print(d)
    a_l.append(d)

print(g_max)

### FIXED CODE ###

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

# 最大公約数
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

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

# 累積GCD
left = [0]*(n+1)
right = [0]*(n+1)
for i in range(n):
    left[i+1] = gcd(left[i], a[i])
for i in reversed(range(n)):
    right[i] = gcd(right[i+1], a[i])

# print(left)
# print(right)

# 集計
ans = 0
for i in range(n):
    l = left[i]
    r = right[i+1]
    ans = max(ans, gcd(l, r))

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

x = int(input())

div = []

i = 1
while i*i <= x:
    if x%i == 0:
        div.append(i)
        if i*i != x:
            div.append(x//i)
    i += 1

for d in div:
    a = 0
    while (a-d)<=0 or 5*((a-d)**4) < x//d:
        a += 1
        b = a-d
        if a**5-b**5 == x:
            print(a, b)
            exit()
        if -a**5+b**5 == x:
            print(-a, -b)
            exit()

### FIXED CODE ###

import math

x = int(input())

a = 0
b = 0
while b**5 > -x:
    b -= 1

while a**5-b**5 != x:
    if a**5-b**5 < x:
        a += 1
    else:
        b += 1
        
print(a, b)
### BUGGY CODE ###

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

next = [[0]*n for _ in range(60)]

for v in range(n):
    next[0][v] = a[v]-1
for d in range(60-1):
    for v in range(n):
        next[d+1][v] = next[d][next[d][v]]
        
v = 0
for d in range(60):
    if k>>d&1:
        v = next[d][v]
        
print(v+1)

### FIXED CODE ###

import numpy as np

def main():
    N,K = map(int,input().split())
    A = [0]
    A += list(map(int,input().split()))
    A = np.array(A)
    
    i = 1
    pas = np.zeros(N)
    pas[0] = i
    k = 1
    pass_set = set(pas)
    while k <= K:
        if A[i] in pass_set:
            rps = np.where(pas==(A[i]))[0]
            ans = A[i]
            break
        pas[k] = A[i]
        pass_set.add(A[i])
        ans = A[i]
        i = A[i]
        k += 1

    if k >= K:
        print(ans)
    else:
        rpnum = (K-rps[0])%(k-rps)
        print(int(pas[rps[0]+rpnum]))

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for i in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    j = 0
    while j < W:
        block_count = 0
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                div_count +=1
                white_count = [0 for s in bin_str if s == "1"]
                white_count.append(0)
                break
        else:
            j+=1
    if min_div_count > div_count:
        min_div_count = div_count
print(min_div_count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for _ in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    
    for j in range(W):
        block_count = 0
        white_list = [0]*len(white_count)
        #print("j:"+str(j))
        is_over = False
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            
            white_list[block_count] += int(choco[k][j])
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                is_over = True

        if max(white_list)>K:
            break


        if is_over:
            div_count += 1
            white_count = white_list


        #print(white_list)   
        #print(white_count)
        #print("div_count"+str(div_count))
        if div_count >= min_div_count:
            break
    else:
        min_div_count = div_count
print(min_div_count)
### BUGGY CODE ###

# B - Sum of Three Integers
def main():
    k, s = map(int, input().split())
    cnt = 0

    for i in range(k+1):
        for j in range(k+1):
            for k in range(k+1):
                if i+j+k == s:
                    cnt += 1
    else:
        print(cnt)



if __name__ ==  "__main__":
    main()

### FIXED CODE ###

# B - Sum of Three Integers
def main():
    k, s = map(int, input().split())
    cnt = 0

    for i in range(k+1):
        for j in range(k+1):
            z = s-i-j
            if 0 <= z <= k:
                cnt += 1
    else:
        print(cnt)



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

def main():
  import sys
  input = sys.stdin.readline
  
  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()))

  AB = [a+b for a in A for b in B]
  AB.sort(reverse = True)
  res = [c+ab for ab in AB[:min(K, len(AB))] for c in C]
  res.sort(reverse = True)
  for r in res[:K]:
    print(r)

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline

  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)
  AB = [a+b for a in A for b in B]
  AB.sort(reverse = True)
  res = [c+ab for ab in AB[:min(K, len(AB))] for c in C]
  res.sort(reverse = True)
  print("\n".join(list(map(str,res[:K]))))

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

import scipy.misc as scm

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

a = sorted(a, reverse=True)

comb = -1
for i in range(n-1):
    if a[i] % 2 == 0:
        max_r = int(a[i]/2)
        if max_r in a:
            c = scm.comb(a[i], max_r)
            if c < comb:
                break
            else:
                a_i = a[i]
                a_j = max_r
                comb = c
        else:
            r_list = a[i+1:]
            flag = 0
            for r in r_list:
                c = scm.comb(a[i], r)
                if c > comb:
                    a_i = a[i]
                    a_j = r
                    flag = 1
                    comb = c
            if flag == 0:
                break
    else:
        max_r1 = int(a[i]/2)
        max_r2 = int(a[i]/2)+1
        if max_r1 in a:
            c = scm.comb(a[i], max_r1)
            if c < comb:
                break
            else:
                a_i = a[i]
                a_j = max_r1
        elif max_r2 in a:
            c = scm.comb(a[i], max_r2)
            if c < comb:
                break
            else:
                a_i = a[i]
                a_j = max_r2
                comb = c
        else:
            r_list = a[i+1:]
            flag = 0
            for r in r_list:
                c = scm.comb(a[i], r)
                if c > comb:
                    a_i = a[i]
                    a_j = r
                    flag = 1
                    comb = c
            if flag == 0:
                break
print(a_i, a_j)


### FIXED CODE ###

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

a = sorted(a, reverse=True)

comb = -1
a_i = a[0]
if a_i % 2 == 0:
    mid = int(a_i/2)
    dif = 10**9
    for i in range(1, n):
        if dif > abs(a[i]-mid):
            dif = abs(a[i]-mid)
            a_j = a[i]
else:
    mid = int(a_i/2)
    dif = 10**9
    for i in range(1, n):
        if a[i] > mid:
            if dif > abs(a[i]-mid-1):
                dif = abs(a[i]-mid-1)
                a_j = a[i]
        else:
            if dif > abs(a[i]-mid):
                dif = abs(a[i]-mid)
                a_j = a[i]

print(a_i, a_j)
### BUGGY CODE ###

def generate_is_prime_sieve(N):
    is_prime = [True]*(N+1)
    is_prime[0] = is_prime[1] = False
    for p in range(2,N+1):
        if is_prime[p]:
            for n in range(2*p,N+1,p):
                is_prime[n] = False
    return is_prime
	
N=generate_is_prime_sieve(10**5+1)
for i in range(int(input())):
	counter=0
	a,b=[int(x) for x in input().split()]
	for i in range(a,b+1):
		if N[i] and N[(i+1)//2]:
			counter+=1
	print(counter)



### FIXED CODE ###

def generate_is_prime_sieve(N):
	is_prime = [True]*(N+1)
	is_prime[0] = is_prime[1] = False
	for p in range(2,N+1):
		if is_prime[p]:
			for n in range(2*p,N+1,p):
				is_prime[n] = False
	dummy=[x for x in is_prime]
	for p in range(2,N+1):
		if is_prime[p] and is_prime[(p+1)//2]:
			dummy[p]=True
		else:
			dummy[p]=False
	return dummy
def partial_sums(N):
	something=generate_is_prime_sieve(N)
	counter=0
	partial_sum=[0]*(N+1)
	for i in range(N+1):
		if something[i]:
			counter+=1
		partial_sum[i]=counter
	return partial_sum	
N=partial_sums(10**5+1)
for i in range(int(input())):
	counter=0
	a,b=[int(x) for x in input().split()]
	print(N[b]-N[a-1])
### BUGGY CODE ###

N = int(input())
A = sorted(map(int, input().split()), reverse=False)
dp = [True] * N

for i in range(N):
    if dp[i]:
        for j in range(i+1, N):
            if A[j] % A[i] == 0:
                dp[j] = False
    if A[i] in A[i+1:]:
        dp[i] = False
print(dp.count(True))


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
count = 0
for k in range(2, N):
    for j in range(1, k):
        if S[k] != S[j]:
            for i in range(0, j):
                if (S[i]!=S[j] and S[i]!=S[k]) and j-i!=k-j:
                    count += 1
        else:
            continue
print(count)

### FIXED CODE ###

N = int(input())
S = input()
r = 0
g = 0
b = 0
for a in range(N):
    if S[a] == "R":
        r += 1
    elif S[a] == "G":
        g += 1
    elif S[a] == "B":
        b += 1
all = r*g*b
count = 0
for i in range(0, N-2):
    for j in range(i+1, N-1):
        k = 2*j-i
        if k < N:
            if S[i]!=S[j] and S[i]!=S[k] and S[j]!=S[k]:
                count += 1
print(all-count)
### BUGGY CODE ###

s = input()
while s.find('ST')!=-1:
    s = s.replace('ST','',1)
print(len(s))


### FIXED CODE ###

s = input()
stack = [s[0]]
for i in range(1,len(s)):
    if len(stack)==0:
        stack.append(s[i])
        continue
    else:
        cur_str = stack[-1]
        new_str = s[i]
        if cur_str+new_str=="ST":
            stack.pop()
        else:
            stack.append(new_str)
print(len(stack))
### BUGGY CODE ###

import bisect
n, m = map(int, input().split())
aas = list(map(int, input().split()))
for i in range(m):
    b, c = map(int, input().split())
    aas.sort()
    idx = bisect.bisect_left(aas, c)
    if idx >= b:
        aas = [c]*b + aas[b:]
    else:
        aas = [c]*idx + aas[idx:]
print(sum(aas))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
aas = sorted(list(map(int, input().split())))
hq = []
for i in range(m):
    b, c = map(int, input().split())
    heapq.heappush(hq,(-c,b))
i = 0
while hq:
    c, b = heapq.heappop(hq)
    c = -c
    for j in range(i,min(n,i+b)):
        if aas[j] < c:
            aas[j] = c
        else:
            print(sum(aas))
            exit()
    i = j + 1
print(sum(aas))
### BUGGY CODE ###

n, p = map(int, input().split()) 
s = input() 

ans = 0

if p == 2:
  for i, si in enumerate(s):
    if int(si) % 2 == 0:
      ans += (i+1)
  print(ans)
  exit()

if p == 5:
  for i, si in enumerate(s):
    if int(si) % 5 == 0:
      ans += (i+1)
  print(ans)
  exit()

rem_dict = {i: 0 for i in range(p)}

for i in range(n):
  rem = int(s[i:]) % p
  rem_dict[rem] += 1

ans = 0
ans += rem_dict[0]
for rem, num in rem_dict.items():
  ans += (num * (num  - 1)) // 2

print(ans)

### FIXED CODE ###

def main():
  n, p = map(int, input().split()) 
  s = input() 

  ans = 0

  if p == 2:
    for i, si in enumerate(s):
      if int(si) % 2 == 0:
        ans += (i+1)
    print(ans)
    exit()

  if p == 5:
    for i, si in enumerate(s):
      if int(si) % 5 == 0:
        ans += (i+1)
    print(ans)
    exit()

  rem_list = [0] * p
  cof = 1
  prev_rem = 0
  
  for i in range(n):
    rem = (int(s[n-1-i]) * cof + prev_rem) %  p
    ans += rem_list[rem]
    if rem == 0:
      ans += 1      
    rem_list[rem] += 1

    prev_rem = rem
    cof *= 10
    cof %= p

  print(ans)

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

import bisect
N = int(input())
*A, = map(int, input().split())
t = [[A[i], i] for i in range(N)]
t.sort()

ta = [v for v, i in t]
ti = [i for v, i in t]

ans = 0
for i in range(N):
    r = N-1-ta[i]
    ri = bisect.bisect_right(ta, r)
    for j in range(i+1, ri):
        if (ta[i]+ta[j]) == abs(ti[i]-ti[j]):
            ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

N = int(input())
*A, = map(int, input().split())

l = Counter([i-A[i] for i in range(N)])
r = Counter([i+A[i] for i in range(N)])

ans = 0
for k, v in l.items():
    ans += v*r[k]
print(ans)
### BUGGY CODE ###

# -*- coding:utf8 -*-

l, r = map(int, input().split())
if (l - r) >= 2019:
    ans = 0
else:
    ans = min([(i * j) % 2019 for i in range(l, r) for j in range(i + 1, r + 1)])
print(ans)

### FIXED CODE ###

# -*- coding:utf8 -*-

l, r = map(int, input().split())
if (l - r) >= 2019:
    ans = 0
else:
    ans = 2018
    for i in range(l, r):
        for j in range(i + 1, r + 1):
            m =  (i * j) % 2019
            if m == 0:
                print(m)
                exit()
            elif m < ans:
                ans = m
print(ans)