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;
struct point {
  long double x, y;
  point() {
    x = 0;
    y = 0;
  }
  bool operator==(const point &b) { return x == b.x and y == b.y; }
  point(long double x1, long double y1) {
    x = x1;
    y = y1;
  }
  long double dist(point b) {
    return sqrt((b.x - x) * (b.x - x) + (y - b.y) * (y - b.y));
  }
  long double dist_kv(point b) {
    return ((b.x - x) * (b.x - x) + (y - b.y) * (y - b.y));
  }
  bool point_on_sig(point &a, point &b) {
    return abs(a.dist(b) - (dist(a) + dist(b))) <= 1e-6;
  }
  long double polar_angle() {
    long double alpha = atan2(y, x);
    long double pi = 3.141592654;
    if (alpha < 0) alpha += 2 * pi;
    return alpha;
  }
};
struct line {
  long double A, B, C;
  line() {
    A = 0;
    B = 0;
    C = 0;
  }
  line(point &a, point &b) {
    A = a.y - b.y;
    B = b.x - a.x;
    C = -A * a.x - B * a.y;
  }
  line(long double a, long double b, long double c) {
    A = a;
    B = b;
    C = c;
  }
  line line_perp_dan_cherez_point(point a) {
    return line(-B, A, -(A * a.y) + B * a.x);
  }
  bool onli(point a) { return A * a.x + B * a.y + C == 0; }
  point intersect_lines(line &a) {
    point p;
    p.x = -(((C * a.B) - (a.C * B)) / ((A * a.B) - (a.A * B)));
    p.y = -(((A * a.C) - (a.A * C)) / ((A * a.B) - (a.A * B)));
    return p;
  }
  bool intersect(line &b) { return A * b.B - B * b.A != 0; }
  bool operator==(line &a) { return A == a.A && B == a.B && C == a.C; }
  long double distance_perpendicular(point &d) {
    return abs(A * d.x + B * d.y + C) / (sqrt(A * A + B * B));
  }
};
struct vc {
  long double x, y;
  vc() {
    x = 0;
    y = 0;
  }
  vc(long double x_, long double y_) {
    x = x_;
    y = y_;
  }
  vc(const point &a) {
    x = a.x;
    y = a.y;
  }
  vc minus(const vc &b) { return vc(x - b.x, y - b.y); }
  long double len() { return sqrt(x * x + y * y); }
  long double scalar(const vc &b) { return x * b.x + y * b.y; }
  long double vector(const vc &b) { return x * b.y - y * b.x; }
  long double angle(const vc &b) { return atan2(vector(b), scalar(b)); }
};
vector<int> top;
void top_sort(int v, vector<int> nodes[], int used[], int colors[]) {
  if (colors[v] == 1) {
    cout << -1;
    exit(0);
  } else if (colors[v] == 0)
    colors[v] = 1;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (used[nodes[v][i]] == 0) top_sort(nodes[v][i], nodes, used, colors);
  }
  top.push_back(v + 1);
  used[v] = 1;
  colors[v] = 2;
}
vector<int> z_function(string s) {
  vector<int> z(s.size());
  for (int i = 1, l = 0, r = 0; i < s.size(); ++i) {
    if (i <= r) z[i] = min(r - i + 1, z[i - l]);
    while (i + z[i] < s.size() && s[z[i]] == s[i + z[i]]) ++z[i];
    if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
  }
  return z;
}
vector<int> p_function(string s) {
  vector<int> p(s.size());
  for (int i = 1; i < s.size(); ++i) {
    int j = p[i - 1];
    while (j > 0 && s[i] != s[j]) j = p[j - 1];
    if (s[i] == s[j]) ++j;
    p[i] = j;
  }
  return p;
}
vector<int> now_ans;
void dfs(int v, vector<int> nodes[], int colors[], int turn) {
  if (colors[v] == 1) {
    now_ans.push_back(0);
    return;
  } else if (colors[v] == 0)
    colors[v] = 1;
  for (int i = 0; i < nodes[v].size(); ++i) {
    if (turn == 1)
      dfs(nodes[v][i], nodes, colors, 2);
    else
      dfs(nodes[v][i], nodes, colors, 1);
  }
  if (nodes[v].empty()) {
    now_ans.push_back(turn);
    return;
  }
  colors[v] = 2;
}
int parents[500000];
void create(int v) { parents[v] = v; }
int find_parent(int v) {
  if (v == parents[v]) return v;
  return find_parent(parents[v]);
}
void join(int a, int b) {
  int x = find_parent(a);
  int y = find_parent(b);
  if (x != y) {
    parents[x] = y;
  }
}
struct triple {
  int a, b, c;
  triple(int z, int x, int v) {
    a = z;
    b = x;
    c = v;
  }
  bool operator<(triple n) { return a < n.a; }
  bool operator>(triple n) { return a > n.a; }
  bool operator==(triple n) { return a == n.a; }
};
vector<int> manac(string s, int shift) {
  int l = 0;
  int r = -1;
  int n = s.size();
  vector<int> ans(n);
  for (int i = 1; i < n; i++) {
    int k = 0;
    if (i <= r) {
      k = min(r - i + shift, ans[r - i + l + shift]);
    }
    while (i - k - 1 >= 0 && i + k + 1 - shift < n &&
           s[i - k - 1] == s[i + k + 1 - shift]) {
      k++;
    }
    if (i + k - shift > r) {
      l = i - k;
      r = i + k - shift;
    }
    ans[i] = k;
  }
  return ans;
}
long long INF = (long long)1e20;
long long degree(long long a, long long k, long long p) {
  long long res = 1;
  long long cur = a;
  while (k) {
    if (k % 2) {
      res = (res * cur) % p;
    }
    k /= 2;
    cur = (cur * cur) % p;
  }
  return res;
}
int main() {
  int n, a, b;
  cin >> n >> a >> b;
  pair<int, int> arr[n];
  for (int i = 0; i < n; ++i) {
    cin >> arr[i].first >> arr[i].second;
  }
  pair<int, int> temp[n];
  for (int i = 0; i < n; ++i) {
    temp[i].first = arr[i].second - arr[i].first;
    temp[i].second = i;
  }
  bool used[n];
  for (int i = 0; i < n; ++i) used[i] = false;
  sort(temp, temp + n);
  int id = 0;
  long long sum = 0;
  int counter = -1;
  int c = b;
  for (id = 0; id < min(b, n); ++id) {
    if (temp[id].first >= 0) {
      id = n;
      break;
    }
    used[temp[id].second] = true;
    counter = temp[id].second;
    --c;
  }
  int reserve = -1;
  if (id + 1 < n) {
    if (temp[id + 1].first < 0) {
      reserve = id + 1;
    }
  }
  for (int i = 0; i < n; ++i) {
    if (used[i])
      sum += arr[i].first;
    else
      sum += arr[i].second;
  }
  long long maxi = sum;
  if (b == 0) {
    cout << sum;
    return 0;
  }
  for (int i = 0; i < n; ++i) {
    if (!used[i]) {
      long long mb = sum;
      mb -= arr[i].second;
      if (counter != -1 and c == 0) {
        mb -= arr[counter].first;
        mb += arr[counter].second;
      }
      long long now = arr[i].first;
      now *= pow(2, a);
      mb += max((long long)arr[i].second, now);
      maxi = max(maxi, mb);
    } else {
      long long mb = sum;
      mb -= arr[i].first;
      long long now = arr[i].first;
      now *= pow(2, a);
      mb += max((long long)arr[i].second, now);
      maxi = max(maxi, mb);
    }
  }
  cout << maxi;
}
