#include<bits/stdc++.h>
using namespace std;
#define lop(i,n) for(ll i=0;i<n;i++)
#define lop1(i,n) for(ll i=1;i<=n;i++)
#define lopr(i,n) for(ll i=n-1;i>=0;i--)
#define ll long long int
#define pb push_back
#define all(v) v.begin(),v.end()
#define IOS  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define F first
#define S second	
#define mem(arr,val) memset(arr,val,sizeof(arr))
#define pii pair<int,int>
#define pll pair<ll,ll>
#define LCM(a,b) (a*b)/__gcd(a,b)
#define mii map<int,int>
#define mll map<ll,ll>
#define ub upper_bound
#define lb lower_bound
#define sz(x) (ll)x.size()
#define ld long double
#define pcnt(x) __builtin_popcountll(x)
const long long I1=1e9;
const long long I2=1e18;
const int32_t M1=1e9+7;
const int32_t M2=998244353;
template<typename T,typename T1>T maxn(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T minn(T &a,T1 b){if(b<a)a=b;return a;}

void solve()
{
  //code begins from here//
  int n,m;
  cin>>n>>m;
  int a[n][n];
  mem(a,0);
  lop(i,m){
      int x,y;
      cin>>x>>y;
      x--;y--;
      a[x][y]=1;
      a[y][x]=1;
  }
  int N = 1<<n;
  vector <bool> v(N,false);
  for (int i =1 ; i<N; i++){
      bool cc = true;
      lop(k,n){
          for (int j=k+1; j<n; j++){
              if((i&(1<<j)) && (i&(1<<k))){
                  if(!a[j][k]) cc=false;
              }
          }
      }
      v[i]=cc;
  }
  vector <int> dp(N,I1);
  dp[0]=0;
  for (int i=1 ; i<N; i++){
      for (int j=i; j; j=(j-1)&i){
         if(v[j])  minn(dp[i],dp[i^j]+1);
      }
  }
  cout<<dp[N-1]<<endl;
}

signed main()
{
    IOS;
    #ifdef MODULO
        initialize();
    #endif
    #ifdef SIEVE
        sieve();
    #endif
    int testcase=1;
   // cin>>testcase;
    while(testcase--) solve();
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int n;
LL m,f[202][202][202],a[2020];
#define INF (1LL<<60)
int main(){
	scanf("%d%lld",&n,&m);
	for (int i=1; i<=n; i++) scanf("%lld",&a[i]);
	
	LL ans = m;
	for (int mod=1; mod<=n; mod++){
		memset(f, -1, sizeof(f));
		f[0][0][0] = 0;
		for (int i=0; i<n; i++){
			for (int j=0; j<=i; j++){
				for (int k=0; k<mod; k++){
					f[i+1][j][k] = max(f[i+1][j][k], f[i][j][k]);
					if (f[i][j][k] == -1) continue;
					int p = (k + a[i+1])%mod;
					f[i+1][j+1][p] = max(f[i+1][j+1][p], f[i][j][k] + a[i+1]);
 				}
			}
		}
		LL p = m%mod;
//		printf("%d %d %d %lld\n",n, mod, p, f[n][mod][p]);
		if (f[n][mod][p]!=-1) ans = min(ans, (m - f[n][mod][p])/mod); 
	}
	printf("%lld\n",ans);
	return 0;
}