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

#define cmax 100000
#define inf 0x3f3f3f3f

using namespace std;
typedef pair<int, int> ii;

int n, t, cm;
ii a[cmax];
int d[cmax];
set <int> S;

int gcd(int a, int b)
{
	if(b == 0) return a;
	else return gcd(b, a % b);
}

int gcm(int a, int b)
{
	long long aux = (long long)a * b;
	aux /= (long long)gcd(a, b);
	return (int)aux;
}

ii calc(ii a, ii b)
{
	int c1 = a.first, p1 = a.second;
	int c2 = b.first, p2 = b.second;
	S.clear();

	while(c1 != c2)
	{
		if(c1 < c2) 
		{
			c1 = c2 - (c2 - c1) % p1;
			if(c1 < c2) c1 += p1;
		}
		else if(c2 < c1)
		{
			c2 = c1 - (c1 - c2) % p2;
			if(c2 < c1) c2 += p2;
		}

		if(max(c1, c2) > t) return ii(inf, inf);
		if(c1 == c2) return ii(c1, gcm(p1, p2));

		if(S.find(abs(c2 - c1)) != S.end()) return ii(inf, inf);
		S.insert(abs(c2 - c1));
	}

	return ii(inf, inf);
}

void back(int config, int nconf, int p)
{
	if(p == n) d[config] = min(d[config], d[nconf] + d[config ^ nconf]);
	else
	{

		if(config & (1 << p)) back(config, nconf * 2 + 1, p + 1);
		back(config, nconf * 2, p + 1);
	}
}
int main()
{
	freopen("vanatoare.in", "r", stdin);
	freopen("vanatoare.out", "w", stdout);
	
	scanf("%d%d", &n, &t); cm = (1 << n) - 1;
	for(int i = 0; i < cmax; i++) a[i] = ii(inf, inf);
	for(int i = 0; i < n; i++) scanf("%d%d", &a[1 << i].first, &a[1 << i].second);

	for(int i = 0; i <= cm; i++)
		if(a[i].first != inf && a[i].second != inf)
			for(int j = 0; j < n; j++)
				if((!(i & (1 << j))) && (a[1 << j].first != inf)) 
					a[i + (1 << j)] = calc(a[i], a[1 << j]);
	
	for(int i = 0; i <= cm; i++)
		if(a[i].first != inf) d[i] = 1;
		else d[i] = inf;

	for(int i = 0; i <= cm; i++) back(i, 0, 0);
	printf("%d\n", d[cm]);
	return 0;
}