Mr. Geek is a greedy seller. He has a stock of N laptops which comprises of both useful and useless laptops. Now, he wants to organize a sale to clear his stock of useless laptops. The prices of N laptops are A_{i }each consisting of positive and negative integers (-ve denoting useless laptops). In a day, he can sell atmost M laptops. Mr. Geek being a greedy seller want to earn maximum profit out of this sale. So, help him maximizing his profit by selling useless laptops.
 
Example 1:
Input:
N=4, M=3
A[] = {-6, 0, 35, 4}
Output:
6
Explanation:
Geek sells the laptops with price -6 and
earns Rs. 6 as profit.
 
Example 2:
Input:
N=5, M=10
A[] = {1, -2, -3, -4, 5}
Output:
9
Explanation:
Geek sells the laptops with price -2,
-3 and -4 and earns Rs. 9 as profit.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxProfit() which takes the array A[], its size N and an integer M as inputs and returns the maximum profit Mr. Geek can earn in a single day.
 
Expected time Complexity: O(NlonN)
Expected time Complexity: O(1)
 
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ M ≤ 10^{5}
-10^{6 }≤ A_{i} ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3



def maxProfit( a, n, m):

    # Your code goes here 

Solutions:
def maxProfit(a, n, m):
	useless_laptops = [price for price in a if price < 0]
	useless_laptops.sort()
	total_profit = 0
	laptops_sold = 0
	for laptop_price in useless_laptops:
		if laptops_sold < m:
			total_profit += laptop_price
			laptops_sold += 1
		else:
			break
	return -total_profit


def maxProfit(a, n, m):
	arr = []
	for i in a:
		if i < 0:
			arr.append(i)
	arr.sort()
	return abs(sum(arr[:m]))


def maxProfit(a, n, m):
	a.sort()
	(sum, x) = (0, min(n, m))
	for i in range(0, x):
		if a[i] < 0:
			sum += abs(a[i])
	return sum


def maxProfit(a, n, m):
	sum = 0
	a.sort()
	s = []
	for i in a:
		if i < 0:
			s.append(i)
	for j in range(len(s)):
		if j < m:
			sum = sum + s[j]
	return abs(sum)


def maxProfit(a, n, m):
	a = sorted(a)
	a = list(filter(lambda x: x < 0, a))
	if len(a) < m:
		return abs(sum(a))
	return abs(sum(a[:m]))


def maxProfit(a, n, m):
	count = []
	for i in range(n):
		if a[i] < 0:
			count.append(a[i])
		else:
			continue
	count.sort()
	if len(count) <= m:
		return abs(sum(count))
	Sum = 0
	j = 0
	while j < m:
		Sum += abs(count[j])
		j += 1
	return Sum


def maxProfit(a, n, m):
	na = []
	for i in a:
		if i < 0:
			na.append(i)
	na.sort()
	if m >= len(na):
		return -1 * sum(na)
	return -1 * sum(na[0:m])


def maxProfit(a, n, m):
	a.sort()
	s = 0
	for i in range(0, n):
		if i < m:
			if a[i] < 0:
				s += abs(a[i])
	return s


def maxProfit(a, n, m):
	a.sort()
	b = []
	sum = 0
	for i in a:
		if i < 0:
			b.append(i)
	for j in range(len(b)):
		if j + 1 <= m:
			sum = sum - b[j]
	return sum


def maxProfit(a, n, m):
	a.sort()
	return -sum((x for x in a[:m] if x < 0))


def maxProfit(a, n, m):
	a.sort()
	i = 0
	sell = 0
	while i < min(n, m):
		if a[i] < 0:
			sell += a[i]
			i += 1
		else:
			break
	return -sell


def maxProfit(a, n, m):
	a.sort()
	c = 0
	k = 0
	for i in range(n):
		if a[i] < 0:
			c = c + a[i]
			k = k + 1
		if k >= m:
			break
	return abs(c)


def maxProfit(a, n, m):
	a.sort()
	profit = 0
	for elem in a[:m]:
		profit -= elem if elem < 0 else 0
	return profit


def maxProfit(a, n, m):
	a.sort()
	max_profit = 0
	for number in a[:m]:
		if number < 0:
			max_profit += number
	return abs(max_profit)


import heapq

def maxProfit(a, n, m):
	heapq.heapify(a)
	sum = 0
	while m > 0 and a:
		if a[0] >= 0:
			break
		elif a[0] < 0:
			sum += a[0]
			heapq.heappop(a)
			m -= 1
	return abs(sum)


def maxProfit(arr, n, m):
	c = 0
	ans = 0
	arr.sort()
	for i in range(n):
		if arr[i] < 0:
			c += 1
			ans += -arr[i]
			if c == m:
				break
	return ans


def maxProfit(a, n, m):
	s = 0
	temp = []
	for i in a:
		if i < 0:
			temp.append(i)
			s += i
	if len(temp) < m:
		return abs(s)
	else:
		temp = sorted(temp)
		return abs(sum(temp[:m]))


def maxProfit(a, n, m):
	a.sort()
	sum = 0
	for i in a:
		if i < 0 and m != 0:
			sum = sum + i
			m -= 1
	return abs(sum)


def maxProfit(a, n, m):
	count = 0
	count1 = 0
	a.sort()
	for i in a:
		if i < 0:
			count = count + abs(i)
			count1 = count1 + 1
			if count1 == m:
				break
	return count


def maxProfit(a, n, m):
	a.sort()
	sum = 0
	for i in range(m):
		try:
			if a[i] < 0:
				sum += a[i]
		except:
			return sum * -1
	return sum * -1


def maxProfit(a, n, m):
	a.sort()
	answer = 0
	x = 0
	for i in a:
		if i < 0 and x < m:
			answer += -i
			x += 1
		else:
			break
	return answer


def maxProfit(a, n, m):
	a.sort()
	summ = 0
	for i in range(m):
		if i < n and a[i] < 0:
			summ += a[i]
	return abs(summ)


def maxProfit(arr, n, m):
	arr.sort()
	c = min(n, m)
	sum = 0
	for i in range(c):
		if arr[i] < 0:
			sum += abs(arr[i])
	return sum


def maxProfit(a, n, m):
	maxp = 0
	temp = 0
	a.sort()
	while m > 0 and a[temp] < 0:
		maxp -= a[temp]
		temp += 1
		m -= 1
		if temp == n:
			break
	return maxp


def maxProfit(a, n, m):
	a.sort()
	l = []
	for i in range(n):
		if a[i] < 0:
			l.append(a[i])
	c = 0
	for i in l[0:m]:
		c = c + abs(i)
	return c


def maxProfit(a, n, m):
	a.sort()
	s = 0
	for j in a[:m]:
		if j < 0:
			s += abs(j)
	return s


def maxProfit(a, n, m):
	s = 0
	a.sort()
	for i in range(n):
		if a[i] < 0 and i < m:
			a[i] = a[i] * -1
			s = s + a[i]
	return s


def maxProfit(a, n, m):
	s = 0
	ma = 0
	a.sort()
	for i in range(min(m, n)):
		s -= a[i]
		ma = max(ma, s)
	return ma


def maxProfit(a, n, m):
	negative = []
	for item in a:
		if item < 0:
			negative.append(item)
	negative.sort()
	return -sum(negative[:m])


def maxProfit(a, n, m):
	minus = []
	for i in a:
		if i < 0:
			minus.append(-1 * i)
	minus.sort(reverse=True)
	while len(minus) > m:
		minus.pop()
	return sum(minus)


def maxProfit(a, n, m):
	l = []
	s = 0
	for i in range(n):
		if a[i] < 0:
			l.append(abs(a[i]))
	l.sort(reverse=True)
	if len(l) < m:
		for i in range(len(l)):
			s += l[i]
	else:
		for i in range(m):
			s += l[i]
	return s


def maxProfit(a, n, m):
	b = sorted(a)
	c = 0
	for i in range(n):
		if b[i] < 0 and i + 1 <= m:
			c = c + -b[i]
	return c


def maxProfit(a, n, m):
	a.sort()
	count = 0
	price = 0
	while count < m:
		if count >= n:
			break
		if a[count] > 0:
			break
		price += a[count]
		count += 1
	return -price


def maxProfit(a, n, m):
	a.sort()
	s = 0
	x = min(m, n)
	for i in range(x):
		if a[i] >= 0:
			break
		s += abs(a[i])
	return s


def maxProfit(a, n, m):
	k = 0
	j = []
	for i in a:
		if i < 0:
			j.append(i)
	j.sort()
	i = 0
	while i < len(j):
		k += j[i]
		i += 1
		if i == m:
			break
	return abs(k)


def maxProfit(a, n, m):
	a.sort()
	ans = 0
	for i in range(min(n, m)):
		if a[i] < 0:
			ans += abs(a[i])
	return ans


def maxProfit(a, n, m):
	l = []
	for i in a:
		if i < 0:
			l.append(i)
	l.sort()
	s = sum(l[:m])
	return abs(s)


def maxProfit(a, n, m):
	c = 1
	s = 0
	a.sort()
	for i in a:
		if c <= m and i < 0:
			c += 1
			s += i
		else:
			break
	return abs(s)


def maxProfit(a, n, m):
	a.sort()
	sum = 0
	j = 0
	for i in a:
		if i < 0 and j < m:
			sum += i
			j += 1
		else:
			break
	return -1 * sum


def maxProfit(a, n, m):
	a.sort()
	sum = 0
	count = 0
	for i in range(n):
		if a[i] < 0:
			count = count + 1
			if count <= m:
				sum += abs(a[i])
	return sum


def maxProfit(a, n, m):
	res = 0
	a.sort()
	i = 0
	for i in range(n):
		if i >= m:
			break
		elif a[i] < 0:
			res += abs(a[i])
	return res


def maxProfit(a, n, m):
	res = 0
	i = 0
	a.sort()
	for elem in a:
		if i >= m:
			break
		if elem < 0:
			res += elem * -1
			i += 1
	return res


def maxProfit(a, n, m):
	a.sort()
	profit = 0
	i = 0
	while m and n:
		if a[i] < 0:
			profit += abs(a[i])
			i += 1
			m -= 1
			n -= 1
		else:
			return profit
	return profit


def maxProfit(a, n, m):
	s = 0
	l = []
	for i in a:
		if i < 0:
			l.append(i)
	l.sort()
	j = 0
	for i in l:
		s -= i
		j += 1
		if j == m:
			return s
	return s


def maxProfit(a, n, m):
	a.sort()
	su = 0
	for i in range(n):
		if m == 0:
			return -su
		if a[i] < 0:
			m -= 1
			su += a[i]
	return -su


def maxProfit(a, n, m):
	a.sort()
	profit = 0
	for i in range(n):
		if m != 0:
			if a[i] < 0:
				profit = profit + a[i]
			m -= 1
	return abs(profit)


def maxProfit(a, n, m):
	s = 0
	b = []
	for i in a:
		if i < 0:
			b.append(-i)
	b.sort()
	b = b[::-1]
	c = 0
	for i in b:
		if c == m:
			return s
		c += 1
		s += i
	return s

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, m) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		print(maxProfit(a, n, m))
		T -= 1
if __name__ == '__main__':
	main()


def maxProfit(a, n, m):
	a.sort()
	summ = 0
	for i in range(0, n):
		if i < m:
			if a[i] < 0:
				summ += abs(a[i])
	return summ

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, m) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		print(maxProfit(a, n, m))
		T -= 1
if __name__ == '__main__':
	main()


def maxProfit(a, n, m):
	ls = []
	for x in a:
		if x < 0:
			ls.append(x)
	ls.sort()
	if m < len(ls):
		return sum(ls[:m]) * -1
	else:
		return sum(ls) * -1

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, m) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		print(maxProfit(a, n, m))
		T -= 1
if __name__ == '__main__':
	main()


def maxProfit(a, n, m):
	x = []
	for i in a:
		if i < 0:
			x.append(i)
	x = sorted(x)
	count = 0
	l = min(m, len(x))
	for i in range(l):
		count += abs(x[i])
	return count

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, m) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		print(maxProfit(a, n, m))
		T -= 1
if __name__ == '__main__':
	main()


def maxProfit(a, n, m):
	res = []
	for itr in range(n):
		if a[itr] < 0:
			res.append(abs(a[itr]))
	res.sort(reverse=True)
	if m > len(res):
		return sum(res)
	else:
		return sum(res[:m])

def main():
	T = int(input())
	while T > 0:
		sz = [int(x) for x in input().strip().split()]
		(n, m) = (sz[0], sz[1])
		a = [int(x) for x in input().strip().split()]
		print(maxProfit(a, n, m))
		T -= 1
if __name__ == '__main__':
	main()


def maxProfit(a, n, m):
	s = 0
	l = []
	for i in a:
		if i < 0:
			l.append(i)
	c = 0
	l.sort()
	for i in range(0, len(l)):
		if c < m:
			s = s + -l[i]
			c = c + 1
	return s


def maxProfit(a, n, m):
	ans = []
	for i in range(n):
		if a[i] < 0:
			ans.append(a[i])
	ans.sort()
	if len(ans) < m:
		return abs(sum(ans))
	else:
		return abs(sum(ans[0:m]))


def maxProfit(a, n, m):
	profit = 0
	(i, count) = (0, 0)
	a.sort()
	while count < m and i < n:
		if a[i] < 0:
			profit += a[i]
			count += 1
		i += 1
	return profit * -1


def maxProfit(a, n, m):
	sum = 0
	a.sort()
	for i in range(m):
		if i < n:
			if a[i] < 0:
				sum += abs(a[i])
			else:
				break
	return sum


def maxProfit(a, n, m):
	a.sort()
	cnt = 1
	ans = 0
	for i in a:
		if i < 0 and cnt <= m:
			ans += abs(i)
			cnt += 1
		if cnt > m:
			break
	return ans


def maxProfit(a, n, m):
	sortedArray = a.sort()
	tot = 0
	i = 0
	while m > 0 and i < n:
		if a[i] < 0:
			tot = tot - a[i]
			m = m - 1
		i = i + 1
	return tot


def maxProfit(a, n, m):
	a.sort()
	p = 0
	if n > m:
		for i in range(m):
			if a[i] < 0:
				p = p - a[i]
	else:
		for i in range(n):
			if a[i] < 0:
				p = p - a[i]
	return p