#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
int dp[1 << 21];
int ind[7][7];
vi mask[21];
int gid(int a, int b) {
    if (a > b) swap(a, b);
    return ind[a][b];
}
int ndp[1 << 21];
int sz[21];
int main() {
    int cnt = 0; 
    for (int i = 1; i <= 6; i++)
        for (int j = i; j <= 6; j++)
            ind[i][j] = cnt++, 
            sz[ind[i][j]] = i * j;
    for (int i = 1; i <= 6; i++)
        for (int j = i; j <= 6; j++) {
            int id = gid(i, j);
            for (int s = 1; s < i; s++)
                mask[id].pb((1 << gid(s, j)) ^ (1 << gid(i - s, j)));
            for (int s = 1; s < j; s++)
                mask[id].pb((1 << gid(i, s)) ^ (1 << gid(i, j - s)));
            sort(mask[id].begin(), mask[id].end());
            mask[id].erase(unique(mask[id].begin(), mask[id].end()), mask[id].end());
        }
    int n, t;
    cin >> n >> t;
    int need = 2 * t;
    int total = 0;
    vi cur;
    for (int i = 1; i <= n; i++) {
        char x[10];
        scanf("%s", x);
        int a = x[0] - '0', b = x[2] - '0';
        total += a * b;
        int nid = gid(a, b);
        cur.pb(nid);
    }
    int waste = total - need;
    sort(cur.begin(), cur.end());
    dp[0] = 0;
    for (int i = 1; i < (1 << 21); i++)
        dp[i] = 1e9;
    for (auto v : cur) {
        //memcpy(ndp, dp, sizeof(dp));
        fill(ndp, ndp + (1 << 21), 1e9);
        for (int j = 0; j < (1 << 21); j++) {
            for (auto h : mask[v])
                chkmin(ndp[j ^ h], dp[j] + 1);
            chkmin(ndp[j ^ (1 << v)], dp[j]);
        }
        memcpy(dp, ndp, sizeof(dp));
    }
    int ans = 1e9;
    //cout << waste << endl;
    for (int i = 0; i < (1 << 21); i++) {
        int was = 0;
        for (int j = 0; j < 21; j++)
            if (i & (1 << j)) was += sz[j];
        if (was <= waste) {
            //if (!dp[i]) cout << "??? " << i << endl;
            chkmin(ans, dp[i]);
        }
    }
    cout << ans << endl;
    return 0;
}
/*
4 15
1x2 2x2 3x3 3x5
6 7
1x2 2x3 1x4 3x2 4x1 6x6
*/