#include <bits/stdc++.h>
using namespace std;
#define int              long long int
#define double           long double
#define print(a)         for(auto x : a) cout << x << " "; cout << endl


const int M = 1000000007;
const int N = 3e5+9;
const int INF = 2e9+1;
const int LINF = 2000000000000000001;

inline int power(int a, int b, int mod=M) {
    int x = 1;
    a %= mod;
    while (b) {
        if (b & 1) x = (x * a) % mod; 
        a = (a * a) % mod;
        b >>= 1;
    }
    return x;
}


//_ ***************************** START Below *******************************




vector<vector<int>> a;

int consistency(int n, int m){
	
    vector<int> fixed(n, 0);
    
    for(int i=0; i<n; i++){
        int x = a[i][0];    
        for(int j=0; j<n; j++){
            int y = a[j][0];
            if(i==j) continue;  
            if(y%x == 0) fixed[i]++;
        }   
    }   
    
    
    vector<vector<int>> dp0(n+1, vector<int>(m+1, 0));
    vector<vector<int>> dp1(n+1, vector<int>(m+1, 0));  
    
    dp0[0][0] = 0;
    dp1[0][0] = 0;  
    
    
    for(int i=1; i<=n; i++){
        int price = a[i-1][1];  
        
        for(int j=0; j<=m; j++){
        	
            dp0[i][j] = max(dp0[i-1][j], dp1[i-1][j]);  
            
            int firstItem = 0;
            if(j-price >= 0)    firstItem = dp0[i][j-price] + 1 + fixed[i-1];  
            
            int atleastTwoItems = 0;
            if(j-price >= 0)    atleastTwoItems = dp1[i][j-price] + 1;  
            
            dp1[i][j] = max(firstItem, atleastTwoItems);
        }
    }   
    
    return max( dp0[n][m], dp1[n][m] );

}















int practice(int n, int m){


    return 0;
}





void solve() {
    
    int n, m;
    cin>> n >> m;
    
    a.resize(n, vector<int>(2));
    for(int i=0; i<n; i++){
    	int x;
    	int y;
    	cin >> x >> y;
    	a[i] = {x,y};
    }
    
    cout << consistency(n, m) << endl;


}





int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}