#include <stdio.h>
#include <vector>

#define x first
#define y second

const int nm = 1 << 16;

using namespace std;


int d[nm], n, t, r[16], p[16], D, conf, sz;
vector<int> v;

void bkt(int, int, int);
int calculeaza(int);
pair<int, int> gcd_e(int, int);

int main()
{
	freopen("vanatoare.in", "r", stdin);
	freopen("vanatoare.out", "w", stdout);

	scanf("%d %d", &n, &t);

	for(int i = 0; i < n; ++i)
	{
		scanf("%d %d", &r[i], &p[i]);
	}

	bkt(0, 0 , 1);
	sz = v.size();
	(void)calculeaza((1 << n) - 1);

	printf("%d\n", d[(1 << n) - 1]);


	return 0;
}

void bkt(int k, int rest, int div)
{
	if(k < n)
	{
		pair<int, int> temp;
		int new_val;
		bkt(k + 1 , rest, div);
		temp = gcd_e(div, p[k]);
		new_val = temp.x * (div / D) * (r[k] - rest) + rest;
	//	printf("%d %d %d\n", k, temp.x, new_val);
		if(new_val % div == rest && new_val % p[k] == r[k])
		{
			rest = new_val;
			div = div / D * p[k];
			if(rest <= t)
			{
				conf |= (1 << k);
				d[conf] = 1;
				v.push_back(conf);
				bkt(k + 1, rest, div);
				conf ^= (1 << k);
			}
		}
	}
}

pair<int, int> gcd_e(int a, int b)
{
	if(b == 0)
	{
		D = a;
		return make_pair(1, 0);
	}
	else
	{
		pair<int, int> temp = gcd_e(b, a % b);
		return make_pair(temp.y, temp.x - a / b * temp.y);
	}
}

int calculeaza(int conf)
{
	int i, min = n;
	int temp;
	if(d[conf])
		return d[conf];
	for(i = 0; i < sz; ++i)
	{
		if((conf & v[i]) == v[i])
		{
			temp = calculeaza(conf ^ v[i]);
			if(min > temp + 1)
			{
				min = temp + 1;
			}
		}
	}
	d[conf] = min;
	
	return d[conf];
}