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.
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const long double eps = 1e-6;
long double sign(long double x) { return (x > 0) - (x < 0); }
long long sign(long long x) { return (x > 0) - (x < 0); }
int sign(int x) { return (x > 0) - (x < 0); }
struct pt {
  long double x, y;
  pt() {}
  pt(long double _x, long double _y) : x(_x), y(_y) {}
  bool operator<(pt p) { return tie(x, y) < tie(p.x, p.y); }
  bool operator==(pt p) { return tie(x, y) == tie(p.x, p.y); }
  pt operator+(pt p) { return {x + p.x, y + p.y}; }
  pt operator-(pt p) { return {x - p.x, y - p.y}; }
  pt operator*(long double d) { return {x * d, y * d}; }
  pt operator/(long double d) { return {x / d, y / d}; }
  long double dot(pt p) { return x * p.x + y * p.y; }
  long double det(pt p) { return x * p.y - y * p.x; }
  long double cross(pt p, pt q) { return (p - *this).det(q - *this); }
  long double dist() { return sqrtl(x * x + y * y); }
  pt rot90() { return pt(-y, x); }
  pt unit() { return *this / dist(); }
  long double angle() { return atan2(y, x); }
  pt rot(long double an) {
    return {x * cos(an) - y * sin(an), x * sin(an) + y * cos(an)};
  }
  void read() { cin >> x >> y; }
  void write() { cout << "(" << x << "," << y << ")" << endl; }
};
struct seg {
  pt fi, sc;
  seg() {}
  seg(pt _fi, pt _sc) : fi(_fi), sc(_sc) {}
  long double dist(pt C) {
    if (fi == sc) return (C - fi).dist();
    long double d = pow((sc - fi).dist(), 2);
    long double t = min(d, max((long double)0.0, (C - fi).dot(sc - fi)));
    return ((C - fi) * d - (sc - fi) * t).dist() / d;
  }
  long double len() { return (fi - sc).dist(); }
  bool on_seg(pt C) {
    return abs(C.cross(fi, sc)) < eps && (fi - C).dot(sc - C) <= eps;
  }
  vector<pt> intersect(seg rhs) {
    long double oa = rhs.fi.cross(rhs.sc, fi);
    long double ob = rhs.fi.cross(rhs.sc, sc);
    long double oc = fi.cross(sc, rhs.fi);
    long double od = fi.cross(sc, rhs.sc);
    if (sign(oa) * sign(ob) < 0 && sign(oc) * sign(od) < 0)
      return {(fi * ob - sc * oa) / (ob - oa)};
    vector<pt> ans;
    if (rhs.on_seg(fi)) ans.push_back(fi);
    if (rhs.on_seg(sc)) ans.push_back(sc);
    if (on_seg(rhs.fi)) ans.push_back(rhs.fi);
    if (on_seg(rhs.sc)) ans.push_back(rhs.sc);
    return ans;
  }
};
struct line {
  long double a, b, c;
  line(pt p1, pt p2) {
    assert(!(p1 == p2));
    a = p2.y - p1.y;
    b = p1.x - p2.x;
    c = a * p1.x + b * p1.y;
  }
  line() {}
  line(long double _a, long double _b, long double _c) : a(_a), b(_b), c(_c) {}
  long double dist(pt p) {
    return fabs(a * p.x + b * p.y - c) / sqrtl(a * a + b * b);
  }
  pair<int, pt> intersect(line rhs) {
    long double dett = a * rhs.b - b * rhs.a;
    if (fabs(dett) <= eps) {
      long double det2 = c * rhs.a - a * rhs.c;
      if (fabs(det2) <= eps) return {-1, pt()};
      return {0, pt()};
    }
    return {1,
            pt((c * rhs.b - rhs.c * b) / dett, (a * rhs.c - c * rhs.a) / dett)};
  }
};
pt reflect(pt A, line L) {
  line perpendicular(-L.b, L.a, -L.b * A.x + L.a * A.y);
  pt insect = perpendicular.intersect(L).second;
  return insect * (long double)2.0 - A;
}
struct mint {
  int val;
  mint() { val = 0; }
  mint(const long long& v) {
    val = (-mod <= v && v < mod) ? v : v % mod;
    if (val < 0) val += mod;
  }
  friend ostream& operator<<(ostream& os, const mint& a) { return os << a.val; }
  friend bool operator==(const mint& a, const mint& b) {
    return a.val == b.val;
  }
  friend bool operator!=(const mint& a, const mint& b) {
    return a.val != b.val;
  }
  friend bool operator<(const mint& a, const mint& b) { return a.val < b.val; }
  friend bool operator>(const mint& a, const mint& b) { return a.val > b.val; }
  friend bool operator<=(const mint& a, const mint& b) {
    return a.val <= b.val;
  }
  friend bool operator>=(const mint& a, const mint& b) {
    return a.val >= b.val;
  }
  mint operator-() { return mint(-val); }
  mint& operator+=(const mint& m) {
    if ((val += m.val) >= mod) val -= mod;
    return *this;
  }
  mint& operator-=(const mint& m) {
    if ((val -= m.val) < mod) val += mod;
    return *this;
  }
  mint& operator*=(const mint& m) {
    val = (val * 1ll * m.val) % mod;
    return *this;
  }
  friend mint pow(mint a, long long p) {
    mint ans = 1;
    for (; p; p /= 2, a *= a)
      if (p % 2 == 1) ans *= a;
    return ans;
  }
  friend mint inv(const mint& a) {
    assert(a.val);
    return pow(a, mod - 2);
  }
  mint& operator/=(const mint& m) { return (*this) *= inv(m); }
  friend mint operator+(mint a, const mint& b) { return a += b; }
  friend mint operator-(mint a, const mint& b) { return a -= b; }
  friend mint operator*(mint a, const mint& b) { return a *= b; }
  friend mint operator/(mint a, const mint& b) { return a /= b; }
};
int solve();
void precomp();
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t = 1;
  if (0) cin >> t;
  if (1) cout << fixed << setprecision(10);
  precomp();
  for (int tc = 1; tc <= t; tc++) {
    if (0 && 0) cout << "Case #" << tc << ": ";
    solve();
  }
}
void precomp() { return; }
int n, a, b, hp[200005], dmg[200005];
bool cmp(int i, int j) {
  if (hp[i] - dmg[i] == hp[j] - dmg[j]) return i < j;
  return hp[i] - dmg[i] > hp[j] - dmg[j];
}
int id[200005];
int solve() {
  cin >> n >> a >> b;
  for (int i = 0; i < n; i++) {
    cin >> hp[i] >> dmg[i];
    id[i] = i;
  }
  sort(id, id + n, cmp);
  long long ans = 0ll;
  for (int i = 0; i < n; i++) {
    if (i < b)
      ans += max(hp[id[i]], dmg[id[i]]);
    else
      ans += dmg[id[i]];
  }
  long long tmp = ans;
  if (b == 0) {
    cout << ans << endl;
    return 0;
  }
  long long times = (1ll << a);
  for (int i = 0; i < n; i++) {
    long long nw = tmp;
    if (i < b) {
      nw -= max(hp[id[i]], dmg[id[i]]);
      nw += hp[id[i]] * 1ll * times;
      ans = max(ans, nw);
    } else {
      nw -= dmg[id[i]];
      nw += hp[id[i]] * times;
      int sc = id[b - 1];
      nw -= max(hp[sc], dmg[sc]);
      nw += dmg[sc];
      ans = max(ans, nw);
    }
  }
  cout << ans << endl;
  return 0;
}
