Recently Max has got himself into popular CCG "BrainStone". As "BrainStone" is a pretty intellectual game, Max has to solve numerous hard problems during the gameplay. Here is one of them:

Max owns n creatures, i-th of them can be described with two numbers — its health hp_{i} and its damage dmg_{i}. Max also has two types of spells in stock:  Doubles health of the creature (hp_{i} := hp_{i}·2);  Assigns value of health of the creature to its damage (dmg_{i} := hp_{i}). 

Spell of first type can be used no more than a times in total, of the second type — no more than b times in total. Spell can be used on a certain creature multiple times. Spells can be used in arbitrary order. It isn't necessary to use all the spells.

Max is really busy preparing for his final exams, so he asks you to determine what is the maximal total damage of all creatures he can achieve if he uses spells in most optimal way.


-----Input-----

The first line contains three integers n, a, b (1 ≤ n ≤ 2·10^5, 0 ≤ a ≤ 20, 0 ≤ b ≤ 2·10^5) — the number of creatures, spells of the first type and spells of the second type, respectively.

The i-th of the next n lines contain two number hp_{i} and dmg_{i} (1 ≤ hp_{i}, dmg_{i} ≤ 10^9) — description of the i-th creature.


-----Output-----

Print single integer — maximum total damage creatures can deal.


-----Examples-----
Input
2 1 1
10 15
6 1

Output
27

Input
3 0 3
10 8
7 11
5 2

Output
26



-----Note-----

In the first example Max should use the spell of the first type on the second creature, then the spell of the second type on the same creature. Then total damage will be equal to 15 + 6·2 = 27.

In the second example Max should use the spell of the second type on the first creature, then the spell of the second type on the third creature. Total damage will be equal to 10 + 11 + 5 = 26.

Difficulty: HARD
Tags: Sorting

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
from sys import stdin

def main():

	def parseints(line):
		return tuple(map(int, line.split()))

	def bdiff(creature):
		return max(0, creature[0] - creature[1])
	(n, a, b) = parseints(input())
	hand = list(map(parseints, stdin.readlines()))
	ans = sum((creature[1] for creature in hand))
	if b:
		hand.sort(key=bdiff)
		best = 0
		if n > b:
			lost = bdiff(hand[n - b])
			for creature in hand[:n - b]:
				best = max(best, (creature[0] << a) - creature[1] - lost)
		for creature in hand[max(0, n - b):]:
			best = max(best, (creature[0] << a) - max(creature))
			ans += bdiff(creature)
		ans += best
	print(ans)
main()


from sys import stdin
from collections import namedtuple

def readline():
	return tuple(map(int, input().split()))
(n, a, b) = readline()
hand = [tuple(map(int, line.split())) for line in stdin.readlines()]
if not b:
	print(sum((creature[1] for creature in hand)))
else:
	hand.sort(key=lambda self: self[0] - self[1])
	best = 0
	if n > b:
		l = hand[n - b]
		lost = max(0, l[0] - l[1])
		for creature in hand[:n - b]:
			best = max(best, (creature[0] << a) - creature[1] - lost)
	for creature in hand[max(0, n - b):]:
		best = max(best, (creature[0] << a) - max(creature))
	print(sum((creature[1] for creature in hand)) + sum((max(0, creature[0] - creature[1]) for creature in hand[max(0, n - b):])) + best)


import sys
read = lambda : map(int, sys.stdin.buffer.readline().split())
(n, a, b) = read()
v = [tuple(read()) for _ in range(n)]
ans = 0
if b > 0:
	c = [v[x][0] - v[x][1] for x in range(n)]
	(w, r) = (list(range(n)), [0] * n)
	w.sort(key=lambda x: c[x], reverse=True)
	for i in range(n):
		r[w[i]] = i
	f = True
	s = 0
	m = min(n, b)
	for i in range(m):
		k = c[w[i]]
		if k <= 0:
			f = False
			m = i
			break
		s += k
	ans = s
	if a > 0:
		for i in range(n):
			k = v[i][0] * (1 << a) - v[i][1]
			tmp = s + k
			if r[i] < m:
				tmp -= c[i]
			elif f:
				tmp -= c[w[m - 1]]
			if tmp > ans:
				ans = tmp
print(sum([v[i][1] for i in range(n)]) + ans)


from sys import stdin
rd = lambda l: tuple(map(int, l.split()))
(n, a, b) = rd(input())
b = min(n, b)
s = list(map(rd, stdin.readlines()))
f = lambda x: max(0, x[0] - x[1])
g = lambda x: (x[0] << a) - x[1]
ans = sum((x[1] for x in s))
mid = 0
if b:
	s.sort(key=f, reverse=True)
	t = sum((f(x) for x in s[:b]))
	for i in range(b):
		mid = max(mid, t - f(s[i]) + g(s[i]))
	for i in range(b, n):
		mid = max(mid, t - f(s[b - 1]) + g(s[i]))
	ans += mid
print(ans)


import sys
(n, a, b) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
creature = [list(map(int, line.decode('utf-8').split())) for line in sys.stdin.buffer]
creature.sort(key=lambda x: -x[0] + x[1])
if b == 0:
	print(sum((x for (_, x) in creature)))
	exit()
base = 0
for i in range(min(n, b)):
	base += max(creature[i])
for i in range(min(n, b), n):
	base += creature[i][1]
ans = base
mul = 1 << a
for i in range(min(n, b)):
	ans = max(ans, base - max(creature[i]) + creature[i][0] * mul)
base = base - max(creature[min(n, b) - 1]) + creature[min(n, b) - 1][1]
for i in range(min(n, b), n):
	ans = max(ans, base - creature[i][1] + creature[i][0] * mul)
print(ans)


def main():
	(n, a, b) = map(int, input().split())
	arr = [0 for _ in range(n)]
	brr = [0 for _ in range(n)]
	for i in range(n):
		(arr[i], brr[i]) = map(int, input().split())
	p = [i for i in range(n)]
	p.sort(key=lambda x: arr[x] - brr[x], reverse=True)
	total = 0
	for i in range(len(arr)):
		if i < b:
			total += max(arr[p[i]], brr[p[i]])
		else:
			total += brr[p[i]]
	if b == 0:
		print(total)
		return
	s = total
	pp = 1 << a
	for i in range(n):
		ctotal = s
		if i < b:
			ctotal -= max(arr[p[i]], brr[p[i]])
			ctotal += arr[p[i]] * pp
		else:
			ctotal -= brr[p[i]]
			ctotal += arr[p[i]] * pp
			ctotal -= max(arr[p[b - 1]], brr[p[b - 1]])
			ctotal += brr[p[b - 1]]
		total = max(total, ctotal)
	print(total)
main()


def well_played():
	(n, a, b) = [int(x) for x in input().split()]
	p = [(0, 0)] * n
	b = min(b, n)
	for i in range(n):
		(h, d) = [int(x) for x in input().split()]
		p[i] = (h, d)
	p.sort(key=lambda x: x[0] - x[1], reverse=True)
	s = 0
	for i in range(b):
		s += max(p[i][0], p[i][1])
	for i in range(b, n):
		s += p[i][1]
	ans = s
	for i in range(b):
		ans = max(ans, s - max(p[i][0], p[i][1]) + (p[i][0] << a))
	s = s - max(p[b - 1][0], p[b - 1][1]) + p[b - 1][1]
	if b:
		for i in range(b, n):
			ans = max(ans, s - p[i][1] + (p[i][0] << a))
	print(ans)
well_played()