#include <fstream>
#include <vector>

using namespace std;

ifstream fin ("vanatoare.in"); ofstream fout ("vanatoare.out");

typedef long long i64;

const int nmax = 16;
const int inf = 1 << 30;

struct str {
    i64 a; int b;
} v[nmax + 1];

str c[(1 << nmax)];
int ok[(1 << nmax)];
int d[(1 << nmax)], vine[(1 << nmax)];

int m;
int cn[nmax + 1];
vector< int > st;

i64 gcd (i64 a, i64 b) {
    while (b > 0) {
        i64 r = a % b;
        a = b;
        b = r;
    }
    return a;
}

void bck (int stn, int pos) {
    if (stn != 0) st.push_back( stn );

    for (int i = pos; i < m; ++ i) {
        bck(stn + (1 << cn[ i ]), i + 1);
    }
}

void eeuclid (i64 a, i64 b, i64 &x, i64 &y, i64 &sol) {
    if (b == 0) {
        x = 1;
        y = 0;
        sol = a;
        return ;
    }
    i64 cat = a / b;
    eeuclid(b, a % b, x, y, sol);
    i64 xx, yy;
    xx = y;
    yy = x - cat * xx;
    x = xx, y = yy;
}

int main() {
    int n, t;
    fin >> n >> t;
    for (int i = 0; i < n; ++ i) {
        fin >> v[ i ].b >> v[ i ].a;
        c[1 << i] = v[ i ];
        ok[1 << i] = v[ i ].b;
    }

    for (int i = 1; i < (1 << n); ++ i) {
        int u = 0;
        for (int j = 0; j < n; ++ j) {
            if (i & (1 << j)) {
                u = j; break;
            }
        }

        int j = i - (1 << u);
        if (j == 0) continue;
        ok[ i ] = -1;
        if (ok[ j ] == -1) continue;

        if (c[ j ].a > t) {
            if (c[ j ].b % v[ u ].a == v[ u ].b) {
                ok[ i ] = c[ j ].b;
            }
            c[ i ] = c[ j ];
        } else {
            i64 D = gcd(c[ j ].a, v[ u ].a);

            i64 p, q, ans, ct = v[ u ].b - c[ j ].b;
            eeuclid(c[ j ].a, v[ u ].a, p, q, ans);

            if (ct % ans == 0) {
                p *= (ct / ans);
                q *= (ct / ans);

                c[ i ].a = 1LL * c[ j ].a * v[ u ].a / D;

                i64 loc = c[ j ].a * p + c[ j ].b;
                loc %= c[ i ].a;
                if (loc < 0) loc += c[ i ].a;

                if (loc <= t) {
                    ok[ i ] = loc;
                    c[ i ].b = loc;
                }
            }
        }
    }

    /*d[ 0 ] = 0;
    for (int i = 1; i < (1 << n); ++ i) {
        m = 0;
        for (int j = 0; j < n; ++ j) {
            if (i & (1 << j))
                cn[ m ++ ] = j;
        }

        st.clear();
        bck(0, 0);

        d[ i ] = inf;
        for (auto j : st) {
            if (ok[ j ] != -1 && d[i - j] + 1 < d[ i ]) {
                d[ i ] = d[i - j] + 1;
                vine[ i ] = i - j;
            }
        }
    }

    fout << d[(1 << n) - 1] << "\n";
    int stn = (1 << n) - 1;

    while (stn != 0) {
        fout << ok[stn - vine[stn]] << " ";
        stn = vine[ stn ];
    }
    fout << "\n";*/

    fin.close();
    fout.close();
    return 0;
}