#include <bits/stdc++.h>
using namespace std;
vector<int> ans;
int bitmask[18];
int bits[20];
int dp[2000000];
bool chMap[2000000];
bool check(int state){

    for (int i=0;i<18;++i)
        if ((bits[i]&state) && (bitmask[i]&state)!=state) return false;
    return true;

}
int solve(int n){
    chMap[0]=true;
    for (int state=1;state<bits[n];++state)
        chMap[state]=check(state);

    dp[0]=0;
    for (int state=1;state<bits[n];++state){
        dp[state]=INT_MAX;
        //if (state%1000==0) cout<<"1000!\n";
        for (int sub=state;sub!=0;sub=(sub-1)&state)
            if (chMap[sub]) dp[state]=min(dp[state],dp[state^sub]+1);
    }
    return dp[bits[n]-1];
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=0;i<20;++i) bits[i]=1<<i;
    for (int i=0;i<m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        u--; v--;
        bitmask[u]|=bits[v];
        bitmask[v]|=bits[u];
    }
    for (int i=0;i<n;++i){
        bitmask[i]|=bits[i];
    }
    printf("%d",solve(n));
}
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
    int n;
    ll x;
    cin >> n >> x;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    ll r = 1LL << 60;
    for (int k = 1; k <= n; k++) {
        int dp[101][100];
        for (int j = 0; j <= k; j++) {
            for (int b = 0; b < k; b++) {
                dp[j][b] = -(1 << 30);
            }
        }
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = min(i + 1, k); j > 0; j--) {
                for (int b = 0; b < k; b++) {
                    int t = (b - a[i]) % k;
                    if (t < 0) t += k;
                    dp[j][b] = max(dp[j][b], dp[j - 1][t] + a[i]);
                }
            }
        }
        int t = dp[k][x % k];
        if (t < 0) continue;
        r = min(r, (x - t) / k);
    }

    cout << r << endl;

    return 0;
}