#!/usr/bin/env python3

# control of heuristic, larger=slower but less greedy
# setting it to 1 gives the bad "mod-2" greedy
# setting it to 2 probably wrong in general but might be correct up to 6x6
# pretty confident 5 should be correct up to 6x6 (but very slow)
HEURISTIC_CAP = 2

def add_piece(state, idx):
    state += 1 << (3*idx)
    if (state >> (3*idx)) & 7 > HEURISTIC_CAP:
        state -= 2 << (3*idx)
    return state

def fix_pair(a, b): return (max(a, b), min(a, b))

pieces = []
piece_id = {}
for w in range(1, 7):
    for h in range(1, w+1):
        pieces.append((w, h))
        piece_id[(w,h)] = piece_id[(h,w)] = len(pieces)

(n, target) = map(int, input().split())
avail = [tuple(map(int, x.split('x'))) for x in input().split()]
start = 0
tot = 0
for (w, h) in avail:
    tot += w*h
    start = add_piece(start, piece_id[(w, h)])
states = {(start, 0): 0}

for (w, h) in reversed(pieces):
    idx = piece_id[(w, h)]
    sub = set()
    for a in range(1, w):
        sub.add(fix_pair(piece_id[(a,h)], piece_id[(w-a,h)]))
    for a in range(1, h):
        sub.add(fix_pair(piece_id[(w,a)], piece_id[(w,h-a)]))
    nstates = {}
    for ((avail, cost), lost) in states.items():
        idx_avail = (avail >> (3*idx)) & 7
        avail -= idx_avail << (3*idx)
        for subset in range(1<<len(sub)):
            rem = idx_avail
            navail = avail
            for (i, (p1, p2)) in enumerate(sub):
                if subset & (1<<i):
                    rem -= 1
                    navail = add_piece(navail, p1)
                    navail = add_piece(navail, p2)
            if rem < 0: continue
            ncost = cost + (idx_avail - rem)
            nlost = lost + (rem % 2)*(w*h)
            if tot - nlost < 2*target: continue
            plost = nstates.get((navail, ncost), 1<<30)
            if nlost < plost:
                nstates[(navail, ncost)] = nlost
    states = nstates
    
print(min(cost for (_, cost) in states))