#include <stdio.h>
#include <string.h>
#include <utility>

#define x first
#define y second

using namespace std;

const int maxn = 65800;

int n, t, a[17], b[17], c[maxn], conf[17];
long long d;

void bkt(int k);
int verifica();
pair<long long, long long> gcd_e(long long one, long long two);
long long max(long long a, long long b)
{
	if(a > b)
		return a;
	return b;
}

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

	int i, j, rep;

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

	for(i = 1; i <= n; ++i)
	{
		scanf("%d %d", &a[i], &b[i]);
	}



	bkt(1);
/*	
	for(i = 1; i < (1 << n); ++i)
	{
		if(c[i])
		{
			for(j = 0; j < n; ++j)
			{
				if(i & (1 << j))
				{
					printf("1");
				}
				else
				{
					printf("0");
				}
			}

		printf("\n");
		}
	}
*/
	for(rep = 1; rep <= 4; ++rep)
	{
		for(i = 1; i < (1 << n); ++i)
		{
			for(j = i + 1; j < (1 << n); ++j)
			{
				if(c[i] && c[j] && !(i & j))
				{
					if(!c[i ^ j] || c[i ^ j] > c[i] + c[j])
					{
						c[i ^ j] = c[i] + c[j];
					}
				}
			}
		}
	}

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



	

	return 0;
}

void bkt(int k)
{
	if(k <= n)
	{
		bkt(k + 1);
		conf[k] = 1;
		if(verifica())
		{
			int temp = 0;
			for(int i = n; i >= 1; --i)
			{
				temp <<= 1;
				temp += conf[i];
			}
			c[temp] = 1;
			bkt(k + 1);
		}
		conf[k] = 0;
	}
}

int verifica()
{
	long long r[5][17], p[5][17];
	pair<long long, long long> temp;
	int i, nr[5], crt = 1;

	memset(r, 0, sizeof(r));
	memset(p, 0, sizeof(p));
	memset(nr, 0, sizeof(nr));

	for(i = 1; i <= n; ++i)
	{
		if(conf[i])
		{
			r[0][++nr[0]] = (long long)a[i];
			p[0][nr[0]] = (long long)b[i];
		}
//		printf("%d ", conf[i]);
	}
//	printf("\n");

	while(nr[crt - 1] > 1)
	{
		for(i = 1; i <= nr[crt - 1]; i += 2)
		{
			++nr[crt];
			if(p[crt - 1][i + 1])
			{
				temp = gcd_e(p[crt - 1][i], p[crt - 1][i + 1]);
				p[crt][nr[crt]] = p[crt - 1][i] / d * p[crt - 1][i + 1];
/*				
				printf("%lld %lld\n", temp.x, temp.y);
				printf("%lld\n", d);
				printf("%lld %lld\n", r[crt - 1][i + 1], r[crt - 1][i]);
				printf("%lld\n", p[crt - 1][i]);
*/				
				r[crt][nr[crt]] = (temp.x * p[crt - 1][i] / d * (r[crt - 1][i + 1] - r[crt - 1][i]) + r[crt - 1][i]) % p[crt][nr[crt]];
				if(r[crt][nr[crt]] < 0)
				{
					r[crt][nr[crt]] += p[crt][nr[crt]];
				}

//				printf("%lld %lld\n", p[crt][nr[crt]], r[crt][nr[crt]]);
				if(r[crt][nr[crt]] > t || (r[crt - 1][i] - r[crt - 1][i + 1]) % d != 0)
				{
					return 0;
				}
			}
			else
			{
				p[crt][nr[crt]] = p[crt - 1][i];
				r[crt][nr[crt]] = r[crt - 1][i];
			}
		}
		++crt;
	}
	return 1;
}

pair<long long, long long> gcd_e(long long one, long long two)
{
	if(two == 0)
	{
		d = one;
		return make_pair(1, 0);
	}
	else
	{
		pair<int, int> temp;
		temp = gcd_e(two, one % two);
		return make_pair(temp.y , temp.x - (one / two) * temp.y);
	}
}