pro-and-con-list

Ted: Robin, get me my legal pad. It's Pros and Cons Time!

There is a long list of n girls in front of Barney, and he is to calculate the optimal "happiness" he can find by selecting exactly 2 girls. (Why 2? No one knows!)

Ted, as a fan of pros and cons, suggests to make a list, a method for estimating the maximum happiness that Barney can achieve. 

Each girl is characterized by two parameters:

- favour: if this girl is chosen, his happiness increases by this amount. 
- anger: if this girl is not chosen, his happiness decreases by this amount.

Find the maximum "happiness" that Barney can obtain. Note that the answer is allowed to be negative.

Input:
The first line of input file contains an integer t, denoting the number of test cases to follow.

The first line of each test case contains an integer n, as explained in statement.
It is followed by n lines, each containing two space-seperated integers denoting the favour and anger of the ith girl.

Output:
The output file should contain t lines, each containing answer for the test case.

Constraints:
1 ≤ t ≤ 10
2 ≤ n ≤ 1e5
0 ≤ favour[i], anger[i] ≤ 1e9
None of the input files exceed 4MB.

SAMPLE INPUT
1
4
2 3
10 2
11 5
4 1

SAMPLE OUTPUT
17

Explanation

Choose girl 2 and 3
happiness = 10 + 11 - 1 - 3 = 17

Difficulty: EASY
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
def HQ(h, a, A):
	return h + a - float(A) / 2


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	list_a = list()
	for i in range(n):
		list_a.append([int(i) for i in input().strip().split(' ')])

	A = sum([i[1] for i in list_a])
	H = sorted([HQ(i[0], i[1], A) for i in list_a], reverse=True)
	print(int(H[0] + H[1]))


t = eval(input())
for _ in range(t):
	n = eval(input())
	h = [0]*n
	s = [0]*n
	c = []
	ans = 0
	for i in range(n):
		h[i], s[i] = list(map(int,input().split()))
		c.append(h[i]+s[i])
	for i in range(2):
		temp = -1
		ind = -1
		for j in range(n):
			if c[j]>temp:
				temp = c[j]
				ind = j
		ans += h[ind]
		h[ind] = -1
		s[ind] = -1
		c[ind] = -1
	for i in s:
		if i > 0:
			ans -= i
	print(ans)
				
			
	


def pro_con(a):
	hap=0
	for i in range(len(a)):
		hap+=(-a[i][1])
	c=[0]*len(a)
	

	for i in range(len(a)):
		c[i]=a[i][0]+a[i][1]
	c.sort()
	return hap+c[-1]+c[-2]
for i in range(eval(input())):
	n=eval(input())
	a=[0]*n
	for i in range(n):
		a[i]=list(map(int,input().split()))
	print(pro_con(a))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
tc = int(input())
for i in range(tc):
	n = int(input())
	sum1 = 0
	sum2 = 0
	angersum = 0
	for j in range(n):
		favour = 0
		anger = 0
		favour, anger = input().split()
		favour = int(favour)
		anger = int(anger)
		angersum = angersum + anger
		total = favour+anger
		if total >= sum1:
			sum2 = sum1
			sum1 = total
		elif total >= sum2:
			sum2 = total
	print(((sum1+sum2) - angersum))


def main():
	effect = [0] * 100000
	total_anger = 0
	tc = int(input())
	while(tc > 0):
		girls = int(input())
		for i in range(girls):
			favour, anger = list(map(int, input().split()))
			total_anger = total_anger + anger
			effect[i] = favour + anger
		solve(girls, total_anger, effect)
		total_anger = 0
		tc -= 1


def solve(girls, total_anger, effect):
	select = 2
	for i in range(select):
		j = i + 1
		for j in range(j, girls, 1):
			if(effect[i] < effect[j]):
				maxi = effect[j]
				effect[j] = effect[i]
				effect[i] = maxi
	#print effect[0], effect[1], total_anger
	ans = effect[0] + effect[1] - total_anger
	print(ans)
main()


def HQ(h, a, A):
	return h + a - float(A) / 2


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	list_a = list()
	for i in range(n):
		list_a.append([int(i) for i in input().strip().split(' ')])

	A = sum([i[1] for i in list_a])
	H = sorted([HQ(i[0], i[1], A) for i in list_a], reverse=True)
	print(int(H[0] + H[1]))


t=eval(input())
i=0
while i<t:
	n=eval(input())
	j=0
	save=-1
	save2=-1
	maxim=0
	maxim2=0
	s=0
	saven=-1
	saven2=-1
	while j<n:
		x=input().split(' ')
		f=int(x[0])
		a=int(x[1])
		s=s+a
		if f+a>=maxim:
			if maxim>=maxim2:
				maxim2=maxim
				save2=save
				saven2=saven
			maxim=f+a
			save=a
			saven=f
		elif f+a>=maxim2:
			maxim2=f+a
			save2=a
			saven2=f
		j=j+1
	s=s-save-save2
	print(saven+saven2-s)
	i=i+1


t = eval(input())

for _ in range(t):
	n = eval(input())
	tn = 0
	P = []
	N = []
	for i in range(n):
		p, r = list(map(int, input().split()))
		tn += r
		P.append(p)
		N.append(r)
	a = P[0] + N[0] - tn
	s = 0
	for i in range(1, n):
		x = P[i] + N[i] - tn
		if x > a:
			a = x
			s = i
	ans = a
	P.pop(s)
	N.pop(s)
	a = P[0] + N[0]
	s = 0
	for i in range(1, n - 1):
		x = P[i] + N[i]
		if x > a:
			a = x
			s = i
	ans += a
	print(ans)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
t=int(input())
while t>0:
	t-=1
	n=int(input())
	l=[]
	m=[]
	for i in range(n):
		a,b=input().split(" ")
		a,b=int(a),int(b)
		l.append(a+b)
		m.append(b)
	l.sort()
	l=l[::-1]
	s=sum(m)
	#print(l[0]+l[1])
	print(l[0]+l[1]-s)
		
	


t=int(input())
while t:
	n=int(input())
	arr=[]
	for i in range(n):
		x,y=list(map(int,input().split()))
		arr.append((x,y))
	x=0
	s=[]
	for i in range(n):
		s.append(arr[i][0]+arr[i][1])
		x+=arr[i][1]
	s=sorted(s)
	print(s[n-1]+s[n-2]-x)
	t-=1
	


T=eval(input())
for _ in range(T):
	N=eval(input())
	a=[list(map(int,input().split())) for x in range(N)]
	b=[]
	for x,y in a:
		b.append((x+y,y))
	b.sort()
	tot=b[-1][0]-b[-1][1]+b[-2][0]-b[-2][1]
	for i in range(N-2):
		tot-=b[i][1]
	print(tot)	


import sys
t = int(sys.stdin.readline())
for test in range(t):
	n = int(sys.stdin.readline())
	first = tuple(map(int, sys.stdin.readline().split()))
	second = tuple(map(int, sys.stdin.readline().split()))
	if sum(first) < sum(second):
		first, second = second, first
	happiness = 0 - first[1] - second[1]
	for girl in range(2, n):
		score = tuple(map(int, sys.stdin.readline().split()))
		happiness = happiness - score[1]
		if sum(score) > sum(first):
			second = first
			first = score
		elif sum(score) > sum(second):
			second = score
	print(happiness + sum(first) + sum(second))


if __name__ == "__main__":
	t = eval(input())
	while t > 0:
		n = eval(input())
		happy = []
		anger = 0
		while n > 0:
			a,b = input().strip().split()
			happy.append(int(a)+int(b))
			anger = anger + int(b) 
			n = n-1
		happy = sorted(happy)
		
		
		print(happy[len(happy)-1]+happy[len(happy)-2]-anger)
		
		t = t -1 


numTest = input()


for i in range(int(numTest)):
	girls = input()
	happy = []
	angry = []
	total = []
	for i in range(int(girls)):
		data = input()
		h = int(data.split(' ')[0])
		a = int(data.split(' ')[1])
		happy.append(h)
		angry.append(a)
		total.append(h+a)
	total_anger = sum(angry)
	total.sort(reverse=True)
	happy = total[0]+total[1] - total_anger
	print(happy)


for _ in range(eval(input())):
	a=[]
	n=eval(input())
	for i in range(n):
		a.append(list(map(int,input().split())))
	c=[]
	tmp=0
	for x,y in a:
		c.append(x+y)
		tmp+=y
	c.sort()
	print(sum(c[-2:])-tmp)



#-------------------------------------------------------------------------------
def main():
	tc = int(input())
	assert(1 <= tc <= 10)
	while tc > 0:
		tc += -1
		N = int(input())
		assert(2 <= N <= 10 **5)
		girls = []
		for i in range(N):
			p_f, p_a = input().split()
			p_f, p_a = int(p_f), int(p_a)
			assert(0 <= p_f <= 10**9)
			assert(0 <= p_f <= 10**9)
			girls.append((i, p_f+p_a, p_f, p_a))

		sorted_girls = sorted(girls, key=lambda i_a_b_c: i_a_b_c[1], reverse=True)
		print(sum([-1*c for (i,a,b,c) in sorted_girls]) + sorted_girls[0][1] + sorted_girls[1][1])


if __name__ == '__main__':
	main()