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 hpi and its damage dmgi. Max also has two types of spells in stock:

  1. Doubles health of the creature (hpi := hpi·2); 
  2. Assigns value of health of the creature to its damage (dmgi := hpi). 



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·105, 0 ≤ a ≤ 20, 0 ≤ b ≤ 2·105) — 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 hpi and dmgi (1 ≤ hpi, dmgi ≤ 109) — 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.
import java.io.*;
import java.util.*;

public class CODEFORCES
{
	@SuppressWarnings("rawtypes")
	static InputReader in;
	static PrintWriter out;

	public static class Pair implements Comparable<Pair>
	{
		long u;
		long v;
		long dif;

		public Pair(long u, long v)
		{
			this.u = u;
			this.v = v;
			dif = u - v;
		}

		public int hashCode()
		{
			int hu = (int) (u ^ (u >>> 32));
			int hv = (int) (v ^ (v >>> 32));
			return 31 * hu + hv;
		}

		public boolean equals(Object o)
		{
			Pair other = (Pair) o;
			return u == other.u && v == other.v;
		}

		public int compareTo(Pair other)
		{
			return Long.compare(other.dif, dif) != 0 ? Long.compare(other.dif, dif) : Long.compare(other.u, u);
		}

		public String toString()
		{
			return u + " " + v;
		}
	}

	static void solve()
	{
		int n = in.ni();
		int a = in.ni();
		int b = in.ni();
		Pair p[] = new Pair[n];
		for (int i = 0; i < n; i++)
			p[i] = new Pair(in.ni(), in.ni());
		Arrays.sort(p);
		long ans = 0;
		int tmp = b;
		for (int i = 0; i < n; i++)
		{
			if (tmp > 0)
				ans += Math.max(p[i].u, p[i].v);
			else
				ans += p[i].v;
			tmp--;
		}
		tmp = b;
		long hh = ans;
		for (int i = 0; i < n; i++)
		{
			if (tmp > 0)
				ans = Math.max(ans, hh - Math.max(p[i].u, p[i].v) + p[i].u * (1L << a));
			else if (b > 0)
				ans = Math.max(ans, hh - Math.max(p[b - 1].u, p[b - 1].v) + p[b - 1].v - p[i].v + p[i].u * (1L << a));
			tmp--;
		}
		out.println(ans);
	}

	static int[][] graph(int from[], int to[], int n, int cn)
	{
		int g[][] = new int[n][];
		int cnt[] = new int[n];
		for (int i = 0; i < cn; i++)
		{
			cnt[from[i]]++;
			// cnt[to[i]]++;
		}
		for (int i = 0; i < n; i++)
			g[i] = new int[cnt[i]];
		Arrays.fill(cnt, 0);
		for (int i = 0; i < cn; i++)
		{
			g[from[i]][cnt[from[i]]++] = to[i];
			// g[to[i]][cnt[to[i]]++] = from[i];
		}
		return g;
	}

	@SuppressWarnings("rawtypes")
	static void soln()
	{
		in = new InputReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}

	static void debug(Object... o)
	{
		System.out.println(Arrays.deepToString(o));
	}

	public static void main(String[] args)
	{
		new Thread(null, new Runnable()
		{
			public void run()
			{
				try
				{
					soln();
				} catch (Exception e)
				{
					e.printStackTrace();
				}
			}
		}, "1", 1 << 26).start();
	}

	// To Get Input
	// Some Buffer Methods
	static class InputReader<SpaceCharFilter>
	{

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream)
		{
			this.stream = stream;
		}

		public int snext()
		{
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars)
			{
				curChar = 0;
				try
				{
					snumChars = stream.read(buf);
				} catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int ni()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nl()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n)
		{
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
			{
				a[i] = ni();
			}
			return a;
		}

		public long[] nextLongArray(int n)
		{
			long a[] = new long[n];
			for (int i = 0; i < n; i++)
			{
				a[i] = nl();
			}
			return a;
		}

		public String readString()
		{
			int c = snext();
			while (isSpaceChar(c))
			{
				c = snext();
			}
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine()
		{
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = snext();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c)
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c)
		{
			return c == '\n' || c == '\r' || c == -1;
		}

		public interface SpaceCharFilter
		{
			public boolean isSpaceChar(int ch);
		}

	}
}