Chef has an array of N integers. He wants to play a special game. In this game he needs to make all the integers in the array greater than or equal to 0. 
Chef can use two types of operations. The first type is to  increase all the integers of the given array by 1, but it costs X coins. The operation of the second type is to add 1 to only one integer of the given array and to use this operation you need to pay 1 coin. You need to calculate the minimal cost to win this game (to make all integers greater than or equal to 0)  

-----Input-----

The first line of the input contains an integer N denoting the number of elements in the given array. The second line contains N space-separated integers A1, A2, ..., AN denoting the given array. The third line contains number X - cost of the first type operation. 


-----Output-----
For each test case, output a single line containing minimal cost required to make all the integers greater than or equal to zero.

-----Constraints-----

- 1 ≤ N ≤ 105
- -109 ≤ Ai ≤  109 
- 0 ≤ X  ≤ 109

-----Example-----
Input:
3
-1 -2 -3
2

Output:
5

-----Explanation-----
Example case 1: Use the first type operation twice and the second type once.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
n = int(input())
l = map(int, input().split())
x = int(input())
l = [i for i in l if i < 0]
l.sort()
print(-sum(l) if -sum(l) <= x else -sum(l[:x]))


n = int(input())
arr = list(map(int, input().split()))
x = int(input())
arr.sort()
sumi = 0
if x == 0:
	print(0)
elif x > n:
	for i in range(n):
		if arr[i] < 0:
			sumi += arr[i]
		else:
			break
	print(abs(sumi))
elif arr[x - 1] < 0:
	print(abs(sum(arr[:x])))
else:
	for i in range(n):
		if arr[i] < 0:
			sumi += arr[i]
		else:
			break
	print(abs(sumi))


N = int(input())
A = list(map(int, input().split()))
X = int(input())
Neg = [_ for _ in A if _ < 0]
Neg.sort(reverse=True)
neg_len = len(Neg)
negative_tot = abs(sum(Neg))
x_count = 0
max_neg = abs(min(Neg))
if X == 0:
	print(0)
elif len(Neg) <= X:
	print(negative_tot)
else:
	x_count = abs(Neg[-X - 1])
	rem = abs(sum(Neg[-X:])) - x_count * X
	print(x_count * X + rem)


n = int(input())
a = list(map(int, input().split(' ')))
x = int(input())
a.sort()
ans = 0
if x == 0:
	ans = 0
elif x < n:
	op1 = max(0, -a[x - 1])
	ans += op1 * x
	for i in range(x - 1):
		ans += max(0, -(a[i] + op1))
else:
	for i in range(n):
		if a[i] < 0:
			ans += -a[i]
print(ans)


n = int(input())
list1 = list(map(int, input().split()))
k = int(input())
summ = 0
count = 0
list2 = []
for i in list1:
	if i < 0:
		count += 1
		summ += i
		list2.append(i)
list2 = sorted(list2, reverse=True)
if k > 1:
	if k < count:
		l = count - k
		m = list2[l - 1]
		print(abs(sum(list2[l:])))
	else:
		print(abs(summ))
else:
	print(abs(list2[count - 1]) * k)


n = int(input())
a = list(map(int, input().split()))
x = int(input())
l = []
for i in a:
	if i < 0:
		l.append(-i)
l.sort()
m = len(l)
ans = 0
if l:
	if x > n:
		ans = sum(l)
	else:
		ans = sum(l[m - x:])
print(ans)


n = int(input())
a = [int(i) for i in input().split() if int(i) < 0]
x = int(input())
a.sort(reverse=True)
na = len(a)
if x == 0:
	print(0)
elif x <= na:
	c = na - x
	print(-a[c] * x + sum([a[c] - i for i in a[c + 1:]]))
else:
	print(-sum(a))


n = int(input())
list_int = [int(i) for i in input().split()]
x = int(input())

def Negative(List):
	return [num for num in List if num < 0]
l = Negative(list_int)
l.sort()
list_sum = sum(l)
if x == 0:
	print(0)
elif x == 1:
	print(-l[0])
elif x < len(l):
	cost = -sum(l[:x])
	print(cost)
else:
	cost = -list_sum
	print(cost)


n = int(input())
a = list(map(int, input().split()))
x = int(input())
b = [x for x in a if x < 0]
(j, minimum) = (len(b), 0)
b.sort(reverse=True)
if x == 0:
	minimum = 0
elif x >= j:
	minimum = -sum(b)
else:
	k = j - x
	minimum = b[k] * (j - 1 - k - x) - sum(b[k + 1:])
print(minimum)


import sys
w = int(input())
num = list(map(int, sys.stdin.readline().split()))
n = int(input())
num.sort()
add = 0
coin1 = 0
coin = 0
for i in range(w):
	if num[i] < 0:
		coin1 += num[i]
		add += 1
if add <= n:
	print(abs(coin1))
else:
	coin = abs(num[n - 1]) * n
	for i in range(n - 1):
		coin += abs(num[i]) - abs(num[n - 1])
	print(coin)


from sys import stdin

def solve():
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	x = int(stdin.readline())
	a.sort()
	ans = 0
	if x == 0:
		ans = 0
	elif x < n:
		op1 = max(0, -a[x - 1])
		ans += op1 * x
		for i in range(x - 1):
			ans += max(0, -(a[i] + op1))
	else:
		for i in range(n):
			if a[i] < 0:
				ans += -a[i]
	print(ans)

def __starting_point():
	solve()
__starting_point()


import numpy as np
n = int(input())
l1 = list(map(int, input().split()))
x = int(input())
l1 = np.array(l1)
l1.sort()
l1 = l1[l1 < 0]
ans = 0
while len(l1) > 0:
	if len(l1) >= x:
		ans += x * -l1[-1]
		l1 += -l1[-1]
		l1 = l1[l1 < 0]
	else:
		ans += -sum(l1)
		break
print(ans)


n = int(input())
a = list(map(int, input().split()))
x = int(input())
lst = []
for i in a:
	if i < 0:
		lst.append(i)
lst.sort()
if -sum(lst) < x:
	print(-sum(lst))
else:
	print(-sum(lst[:x]))


nums = int(input())
numbers = input().split(' ')
numbers = [int(x) for x in numbers]
x = int(input())
numbers.append(0)
numbers = sorted(numbers)
inc = 0
cost = 0
negative_nums = 0
max_negative = 0
for n in numbers:
	if n + inc < 0:
		negative_nums += 1
		max_negative = n + inc
while negative_nums > x:
	cost += x * abs(numbers[x - 1])
	inc += abs(numbers[x - 1])
	negative_nums = 0
	max_negative = 0
	for n in numbers:
		if n + inc < 0:
			negative_nums += 1
			max_negative = n + inc
if negative_nums <= x:
	for n in numbers:
		if n + inc < 0:
			cost += (n + inc) * -1
print(cost)


N = int(input())
A = list([x for x in map(int, input().split()) if x < 0])
X = int(input())
coins = 0
if len(A) <= X:
	coins += abs(sum(A))
else:
	A.sort(reverse=True)
	coins = abs(sum(A[len(A) - X:]))
print(coins)


import sys
import heapq

def main():
	from sys import stdin, stdout
	f = stdin.readline().strip()
	s = stdin.readline().strip()
	t = stdin.readline().strip()
	n = heapq.nsmallest(int(t), [int(x) for x in s.split(' ') if int(x) < 0])
	if len(n) > int(t):
		heapq.heapify(n)
		r = heapq.heappop(n) * -1
		stdout.write(str(int(t) * r + sum([x + r for x in n]) * -1) + '\n')
	else:
		stdout.write(str(sum(n) * -1) + '\n')
	return 0
main()


import bisect

def solve(n, arr, x):
	if x == 0:
		return 0
	num_negative = 0
	negative_sorted = []
	sum_negative = 0
	for i in range(len(arr)):
		if arr[i] < 0:
			sum_negative += arr[i]
			bisect.insort(negative_sorted, arr[i])
	if x >= len(negative_sorted):
		return -1 * sum_negative
	z = len(negative_sorted) - x
	sum_negative -= negative_sorted[z] * x
	sum_negative += negative_sorted[z] * x
	for i in range(0, z):
		sum_negative -= negative_sorted[-i - 1]
	return -1 * sum_negative
N = input()
Arr = list(map(int, input().split()))
X = int(input())
print(solve(N, Arr, X))


n = int(input())
arr = list(map(int, input().split()))
x = int(input())
l = []
for i in arr:
	if i < 0:
		l.append(i)
l.sort(reverse=True)
s = 0
inc = 0
z = len(l)
for i in range(len(l)):
	if x <= z:
		l[i] += inc
		s += abs(l[i]) * x
		inc += abs(l[i])
		z -= 1
	else:
		l[i] += inc
		s += abs(l[i])
print(s)


N = int(input())
A = list(filter(lambda x: x < 0, map(int, input().split())))
X = int(input())
coins = 0
if len(A) <= X:
	coins += abs(sum(A))
else:
	A.sort(reverse=True)
	coins = abs(sum(A[len(A) - X:]))
print(coins)


n = int(input())
L = list(map(int, input().split()))
x = int(input())
A = []
for i in L:
	if i < 0:
		A.append(abs(i))
if len(A) <= x:
	ans = sum(A)
	print(ans)
elif x == 0:
	print(0)
else:
	A.sort()
	a = A[len(A) - x]
	ans = a * x
	for i in range(len(A) - x + 1, len(A)):
		ans += A[i] - a
	print(ans)


import sys
import math

def f(x):
	if x >= 0:
		return 10 ** 10
	return math.fabs(x)
N = int(sys.stdin.readline())
L = list(map(int, sys.stdin.readline().split()))
X = int(sys.stdin.readline())
L.sort(key=f)
j = N
s = 0
Sums = []
for i in range(N):
	if L[i] >= 0:
		j = i
		break
	s += math.fabs(L[i])
	Sums.append(s)
if X == 0:
	print(0)
else:
	c = j - X + 1
	ans = 0
	if c > 0:
		ans += math.fabs(L[c - 1]) * X
		ans += s - Sums[c - 1] - math.fabs(L[c - 1]) * (j - c)
	else:
		ans += s
	sys.stdout.write(str(int(ans)))


n = int(input())
a = list(map(int, input().split()))
x = int(input())
if min(a) >= 0:
	print(0)
else:
	temp = []
	for i in a:
		if i < 0:
			temp.append(i)
	l = len(temp)
	temp.sort(reverse=True)
	ops = 0
	rem = l
	i = 0
	while i < l and rem > x:
		if ops >= abs(temp[i]):
			rem -= 1
			i += 1
			continue
		else:
			opsneed = abs(temp[i]) - ops
			ops += opsneed
			rem -= 1
			i += 1
			continue
	ans = ops * x
	i = l - rem
	while i < l:
		ans += abs(temp[i]) - ops
		i += 1
	print(ans)


n = int(input())
a = list(map(int, input().split()))
x = int(input())
l1 = [i for i in a if i < 0]
l1.sort()
l1.reverse()
if len(l1) > x and x > 0:
	i = len(l1) - x
	l2 = l1[0:i]
	l1 = l1[i:]
	cnt1 = abs(sum(l2)) * x - abs(sum(l2[0:i - 1]) * x)
	cnt2 = abs(sum(l1)) - cnt1 // x * len(l1)
	cnt = cnt1 + cnt2
	print(cnt)
elif x == 0:
	print(0)
else:
	print(abs(sum(l1)))


n = int(input())
l = [int(i) for i in input().split()]
x = int(input())
l.sort()
if l[0] >= 0:
	print(0)
else:
	cnt = 0
	cost = 0
	for i in l:
		if i < 0:
			cnt += 1
		else:
			break
	l = l[0:cnt]
	if x >= len(l):
		print(sum(l) * -1)
	else:
		k = min(l[x:len(l)])
		cost += -1 * k * x
		tmp = l[0:x]
		tmp = [i - k for i in tmp]
		for i in tmp:
			cost += max(0, -1 * i)
		print(cost)


n = int(input())
a = [int(x) for x in input().split()]
x = int(input())
l = []
c = 0
for i in range(n):
	if a[i] < 0:
		l.append(-a[i])
l.sort()
ll = len(l)
num = ll - x
ans = 0
for i in range(len(l)):
	l[i] = c - l[i]
	if ll > x:
		ans += abs(l[i] * x)
		c += abs(l[i])
	else:
		ans += abs(l[i] * ll)
		c += abs(l[i])
	ll -= 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
x = int(input())
count = 0
k = []
for i in range(n):
	if l[i] < 0:
		count += 1
		k.append(l[i])
y = count
k.sort()
z = y - x
k.reverse()
sum = 0
h = 0
for i in range(len(k)):
	k[i] += h
	if y > x:
		sum += abs(k[i] * x)
		h += abs(k[i])
	else:
		sum += abs(k[i] * y)
		h += abs(k[i])
	y -= 1
print(sum)


n = int(input())
l = list(map(int, input().split()))
x = int(input())
k = []
for i in l:
	if i < 0:
		k.append(i)
c = len(k)
ans = 0
if c >= x:
	if x == 0:
		print(0)
	else:
		k.sort()
		m = k[x - 1]
		ans += -1 * m * x
		for j in range(len(k)):
			k[j] += -1 * m
		for j in k:
			if j < 0:
				ans += -1 * j
		print(ans)
else:
	ans += -1 * sum(k)
	print(ans)


n = int(input())
arr = list(map(int, input().split()))
x = int(input())
flag = 0
for i in range(len(arr)):
	if arr[i] < 0:
		arr[flag] = arr[i]
		flag += 1
del arr[flag:]
arr.sort(reverse=False)
if len(arr) > 0:
	print(-sum(arr[:x]))
else:
	print(0)


n = int(input())
a = [int(i) for i in input().split(' ')]
x = int(input())
a.sort(reverse=True)
final = 0
if x == 0 or a[n - 1] >= 0:
	print(0)
elif x < n and a[n - x - 1] < 0:
	p = abs(a[n - x - 1])
	final = p * x
	for i in range(n - x, n):
		final += abs(a[i]) - p
	print(final)
else:
	for i in a:
		if i < 0:
			final += abs(i)
	print(final)


import sys
n = int(sys.stdin.readline())
aa = [int(a) for a in sys.stdin.readline().split()]
x = int(sys.stdin.readline())
aa.extend((0, 1))
aa.sort()
rest = 0
kx = -aa[0]
j = 0
cost = []
while kx >= 0:
	cost.append(kx * x + rest)
	j += 1
	rest += j * (kx + aa[j])
	kx = -aa[j]
print(min(cost) if cost else 0)


T = int(input())
A = map(lambda a: -int(a), input().split())
A = list(filter(lambda a: a > 0, A))
A.sort()
X = int(input())
minimal_cost = 0
if X == 0:
	pass
elif X <= len(A):
	minimal_cost = A[len(A) - X] * X
	for i in range(len(A) - X + 1, len(A)):
		minimal_cost += A[i] - A[len(A) - X]
else:
	for i in range(0, len(A)):
		minimal_cost += A[i]
print(minimal_cost)


from typing import List

def soln(x: int, arr: List[int]) -> int:
	negs = [-1 * i for i in arr if i < 0]
	if not negs:
		return 0
	if x <= 1:
		return x * min(negs)
	negs.sort()
	minm = op1 = sum(negs)
	n = len(negs)
	mul = cur = diff = 0
	for i in negs:
		op1 -= (i - diff) * n
		n -= 1
		cur = i - diff
		diff += cur
		minm = min(minm, op1 + diff * x)
	return minm
n = int(input())
arr = list(map(int, input().split()))
x = int(input())
print(soln(x, arr))


n = int(input())
a = list(map(int, input().strip().split(' ')))
x = int(input())
c = []
numberofnegative = 0
for i in a:
	if i < 0:
		numberofnegative += 1
		c.append(i)
t = len(c)
if numberofnegative < x:
	s = sum(c[:])
	print(-1 * s)
else:
	c.sort()
	s = sum(c[:x])
	print(-1 * s)


n = int(input())
l = [int(i) for i in input().split()]
x = int(input())
l1 = sorted([i for i in l if i < 0])
k = sum((i < 0 for i in l))
if k <= x:
	print(-sum((i for i in l if i < 0)))
else:
	elem = -l1[x - 1]
	ans = elem * x
	for i in range(x - 1):
		ans += abs(l1[i]) - elem
	print(ans)


__author__ = 'TheCodeBuster'
n = int(input())
a = input().split()
x = int(input())
a = list(map(int, a))
b = []
totalcost = 0
for each in a:
	if each < 0:
		b.append(each)
b = sorted(b)
if len(b) >= x:
	totalcost = b[x] * x
	d = b[0:x]
	d = list(map(lambda w: w - b[x], d))
else:
	d = b[0:]
for j in d:
	totalcost = totalcost + j
totalcost = abs(totalcost)
print(totalcost)


def pos(lst):
	return [x for x in lst if x < 0]
N = int(input())
List1 = [int(x) for x in input().split()]
X = int(input())
Sum = 0
List = pos(List1)
List.sort()
if len(List) > X:
	Sum += -1 * List[X] * X
	for i in range(X):
		Sum += -1 * List[i] + List[X]
else:
	Sum += -1 * sum(List)
print(Sum)


n = int(input())
k = n + 1
total = 0
a = list(map(int, input().split()))
x = int(input())
a.sort(reverse=True)
for i in range(n):
	if a[i] < 0:
		k = i
		break
a = a[k:]
if a:
	n = len(a)
	if x > n:
		total -= sum(a)
	else:
		total -= sum(a[n - x:])
print(total)


n = int(input())
number = input()
x = int(input())
number = number.split(' ')
num = []
for i in range(0, n):
	temp = int(number[i])
	if temp < 0:
		num.append(temp)
num.sort()
n = len(num)
min_cost = 0
cost = 0
for i in range(0, n):
	if i == 0:
		min_cost = abs(num[i]) * x
	else:
		cost = abs(num[i]) * x + abs(num[i - 1] - num[i] * i)
		if cost < min_cost:
			min_cost = cost
		num[i] = num[i - 1] + num[i]
if abs(num[n - 1]) < min_cost:
	min_cost = abs(num[n - 1])
print(min_cost)


n = int(input())
a = list(map(int, input().split()))
x = int(input())
c = 0
s = 0
ans = 0
b = []
for i in range(n):
	if a[i] < 0:
		c += 1
		s += a[i]
		b.append(abs(a[i]))
if c <= x:
	print(abs(s))
else:
	b.sort()
	for i in range(0, x):
		ans += b[len(b) - 1 - i]
	print(ans)


import sys
f = sys.stdin
N = int(f.readline())
A = list(map(int, f.readline().split()))
X = int(f.readline())
AA = []
for item in A:
	if item < 0:
		AA.append(-1 * item)
L = len(AA)
if L == 0 or X == 0:
	print(0)
else:
	AA.sort()
	i = L - X
	ans = sum(AA[i:i + X])
	print(ans)


input()
numbers = sorted([-int(x) for x in input().split() if int(x) < 0])
flash_cost = int(input())
flash_count = numbers[len(numbers) - flash_cost - 1] if flash_cost <= len(numbers) else 0
print(flash_count * flash_cost + sum([x - flash_count for x in numbers if x - flash_count > 0]))