#include<bits/stdc++.h>
typedef long long ll;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define pb push_back
#define  lsb(x) ((x) & (-x))
#define  PI acos(-1)
#define  line cout << endl;
#define  getbit(n, i) (((n) & (1LL << (i))) != 0)
#define  resetbit(n, i) ((n) & (~(1LL << (i))))
#define  setbit(n, i) ((n) | (1LL << (i)))
#define  togglebit(n, i) ((n) ^ (1LL << (i)))
const ll mod = (ll) 1e9+7; 
using namespace std;


int main()
{
    int N,T;
    cin >> N >> T;
    vector<ll> A,B;

    for(int i=0;i<N;i++)
     {
        if (i<N/2) {
            int a;
            cin >> a;
            A.push_back(a);
        }
        else {
            int b;
            cin >> b;
            B.push_back(b);
        }
    }
    
    vector<ll> C,D;

    for(int bit=0; bit< (1 << A.size()) ;bit++)
     {
        ll sum = 0;
         for(int i=0; i<  A.size() ;i++)
       {
            if (bit & 1<<i) {
                sum += A[i];
            }
        }
        C.push_back(sum);
    }
    for(int bit=0; bit< (1 << B.size()) ;bit++)
     {
        ll sum = 0;
         for(int i=0; i<  B.size() ;i++)
       {
            if (bit & 1<<i) {
                sum += B[i];
            }
        }
        D.push_back(sum);
    }


    sort(D.begin(),D.end());
    ll ans = 0;
   for(int i=0; i<  C.size() ;i++)
    {
        ll res = T-C[i];
        if (res>0)
         {
            int idx = upper_bound(D.begin(),D.end(),res) - D.begin();
            if (idx>0)
            {
                res -= D[idx-1];
            }
            ans = max(ans,T-res);
        }
    }
    cout << ans << endl;
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

template <typename T> inline void read(T &x)
{
	int f = 1; x = 0; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
	for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	x *= f;
}

const int N = 1e3 + 5;

vector <int> Edge[N][26];

int n, m;
struct info { int x, y; } E[N];

int dis[N][N];
queue < pair <int, int> > q;
bool inq[N][N];

inline void spfa()
{
	memset(dis, 0x3f, sizeof(dis));
	dis[1][n] = 0; q.push(make_pair(1, n)); inq[1][n] = 1;
	
	int x, y;
	while (!q.empty())
	{
		x = q.front().first, y = q.front().second; q.pop(); inq[x][y] = 0;
		
		for (int p = 0; p < 26; p++)
		for (int i = 0; i < (int) Edge[x][p].size(); i++)
		for (int j = 0; j < (int) Edge[y][p].size(); j++)
		{
			int px = Edge[x][p][i], py = Edge[y][p][j];
			if (dis[x][y] + 2 < dis[px][py])
			{
				dis[px][py] = dis[x][y] + 2;
				if (!inq[px][py])
				{
					inq[px][py] = 1;
					q.push(make_pair(px, py));
				}
			}
		}
	}
}

int main()
{
	read(n); read(m);
	char s[2];
	for (int i = 1; i <= m; i++)
	{
		read(E[i].x); read(E[i].y); scanf ("%s", s);
		
		int p = s[0] - 'a';
		Edge[E[i].x][p].push_back(E[i].y);
		Edge[E[i].y][p].push_back(E[i].x);
	}
	spfa();
	int ans = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++) ans = min(ans, dis[i][i]);
	for (int i = 1; i <= m; i++)
	{
		int x = E[i].x, y = E[i].y;
		ans = min(ans, dis[x][y] + 1);
		ans = min(ans, dis[y][x] + 1);
	}
	if (ans == 0x3f3f3f3f) puts("-1");
	else printf ("%d\n", ans);
	return 0;
} 