#include <bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 2e1 + 5;

int fa[MAXN];
int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) { 
    fa[find(y)] = find(x); 
}

vector<int> vec;
int res, col[MAXN];
int n, m, g[MAXN][MAXN];
void dfs(int k) {
	if (k == vec.size()) {
		++res;
		return ;
	}
	for (int i = 1; i <= 3; ++i) {
		int u = vec[k];
		col[u] = i;
		auto check = [](int x) -> bool {
			for (int i = 1; i <= n; ++i) 
				if (g[x][i] && col[i] == col[x])
					return false;
			return true;
		};
		if (check(vec[k])) dfs(k + 1);
		col[u] = 0;
	}
}
bool vis[MAXN];
signed main(int argc, char *argv[]) {
	//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	for (int i = 0; i < MAXN; ++i) fa[i] = i;
	cin >> n >> m;
	while (m--) {
		int u, v;
		cin >> u >> v;
		merge(u, v);
		g[u][v] = g[v][u] = 1;
	}
	int ans = 1;
	for (int i = 1; i <= n; ++i) {
		if (vis[i]) continue;
		vec.clear(), res=  0;
		for (int j = 1; j <= n; ++j) 
			if (find(j) == i) vec.push_back(j), vis[j] = true;;
		dfs(0);
		ans *= res;
	}
	cout << ans << '\n';
	system("pause");
	return 0;
}
#include <cstdio>
int n, x, sum, a, b;
int main() {
    scanf("%d%d", &n, &x);
    x *= 100;
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &a, &b);
        sum += a*b;
        if(sum > x) return printf("%d", i), 0;
    }
    puts("-1");
}