#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
#define rep(i, n) for(int i=0;i<n;i++)
#define all(i, v) for(auto& i : v)
typedef long long ll;
using namespace std;
const ll mod=1000000007, INF=(1LL<<60);
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n, m, a, b;
    cin >> n >> m;
    bool ok[n][n];
    memset(ok, 0, sizeof(ok));
    rep(i, m){
        cin >> a >> b;
        a--; b--;
        ok[a][b] = ok[b][a] = true;
    }
    rep(i, n) ok[i][i] = true;
    m = 1 << n;
    bool connect[m];
    memset(connect, 0, sizeof(connect));
    connect[0] = 1;
    rep(bit, m){
        rep(i, n) if(bit >> i & 1){
            if(!connect[bit - (1 << i)]) continue;
            bool c = true;
            rep(j, n) if(bit >> j & 1){
                if(!ok[i][j]) c = false;
            }
            if(c){
                connect[bit] = true;
                break;
            }
        }
    }


    int cost[m];
    rep(i, m) cost[i] = 20;
    cost[0] = 0;
    rep(bit, m){
        if(connect[bit]) {
            cost[bit] = 1;
            continue;
        }
        int i = (bit - 1) & bit;
        for(;i>=1;i=(i-1)&bit){
            cost[bit] = min(cost[bit], cost[i] + cost[bit - i]);
        }
    }
    cout << cost[m - 1] << endl;
    return 0;
}



#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <set>
#include <sstream>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, s, n) for (int i = s; i < n; i++)
#define debug(s, param) std::cerr << s << param << std::endl;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

const int INF = 1e9;
const ll INFL = 1e18;
const ll MOD = 1000000007;

int main() {
  ll n, k; cin >> n >> k;
  map<ll, ll> m;
  rep (i, n) {
    ll a, b; cin >> a >> b;
    m[a] += b;
  }
  ll ans = 0;
  ll current = 0;
  for (auto [village, money] : m) {
    ll cost = village - current;
    if (k >= cost) {
      ans = village;
      k -= cost;
    } else {
      ans += k;
      k = 0;
      break;
    }
    k += money;
    current = village;
  }
  ans += k;
  cout << ans << endl;
  return 0;
}
