#include<bits/stdc++.h>
using namespace std;
inline long long read(){
    long long x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
struct node{
	long long A,B;
}v[200100];
bool cmp(node a,node b){
	return a.A<b.A;
}
int main(){
	long long n=read(),k=read();
	for(int i=1;i<=n;++i)v[i].A=read(),v[i].B=read();
	sort(v+1,v+1+n,cmp);
	int i;
	v[0].A=0;
	for(i=1;i<=n;++i){
		if(k<v[i].A-v[i-1].A){
			break;
		}
		k-=v[i].A-v[i-1].A;k+=v[i].B;
	}
	--i;
	cout<<v[i].A+k<<endl;
    return 0;
}
#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = (1 << 18);
int n, m;
bool matrix[18][18], good[MAXN];
int dp[MAXN];

bool check(int x) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (j != i)
                if (((x >> i) & 1) && ((x >> j) & 1) && !matrix[i][j])
                    return false;
    return true;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        matrix[a][b] = matrix[b][a] = 1;
    }
    memset(dp, 0x3f3f3f3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i < (1 << n); i++)
        if (check(i)) good[i] = 1, dp[i] = 1;
    for (int i = 1; i < (1 << n); i++) {
        if (good[i]) continue;
        for (int j = i; j; j = (j - 1) & i)
            dp[i] = min(dp[i], dp[j] + dp[i ^ j]);
    }
    cout << dp[(1 << n) - 1];
    return 0;
}