human
Denis, after buying flowers and sweets (you will learn about this story in the next task), went to a date with Nastya to ask her to become a couple. Now, they are sitting in the cafe and finally... Denis asks her to be together, but ... Nastya doesn't give any answer. 

The poor boy was very upset because of that. He was so sad that he punched some kind of scoreboard with numbers. The numbers are displayed in the same way as on an electronic clock: each digit position consists of 7 segments, which can be turned on or off to display different numbers. The picture shows how all 10 decimal digits are displayed: 


After the punch, some segments stopped working, that is, some segments might stop glowing if they glowed earlier. But Denis remembered how many sticks were glowing and how many are glowing now. Denis broke exactly k segments and he knows which sticks are working now. Denis came up with the question: what is the maximum possible number that can appear on the board if you turn on exactly k sticks (which are off now)? 

It is allowed that the number includes leading zeros.

Input

The first line contains integer n (1 ≤ n ≤ 2000) — the number of digits on scoreboard and k (0 ≤ k ≤ 2000) — the number of segments that stopped working.

The next n lines contain one binary string of length 7, the i-th of which encodes the i-th digit of the scoreboard.

Each digit on the scoreboard consists of 7 segments. We number them, as in the picture below, and let the i-th place of the binary string be 0 if the i-th stick is not glowing and 1 if it is glowing. Then a binary string of length 7 will specify which segments are glowing now.


Thus, the sequences "1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011" encode in sequence all digits from 0 to 9 inclusive.

Output

Output a single number consisting of n digits — the maximum number that can be obtained if you turn on exactly k sticks or -1, if it is impossible to turn on exactly k sticks so that...
from  What is a the maximum possible number that can appear on the board if you turn on exactly k sticks (which are off now)?
assistant
#Here is the maximum possible number that can appear on the board if you turn on exactly k sticks (which are off now).
sys import setrecursionlimit
from functools import lru_cache

# def noop(*object): return
# print = noop

def main():
    # T = read_int()
    # for case_idx in range(T):
    ans = solve_case()
    print(ans)

def solve_case():
    n, k = read_int_list()
    digits = read_lines(n, read_str)

    num_to_digit = ["1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011"]
    # valid_digits = set(num_to_digit)

    digit_to_num = dict()
    for num in range(10):
        digit_to_num[num_to_digit[num]] = num

    def is_valid_digit(digit):
        return digit in num_to_digit

    @lru_cache(maxsize=None)
    def cost_to_transform(digit, target_digit):
        need_sticks = 0
        for stick_idx in range(7):
            if target_digit[stick_idx] == '0':
                if digit[stick_idx] == '0':
                    pass
                else:
                    return -1
            else:
                if digit[stick_idx] == '0':
                    need_sticks += 1
                else:
                    pass
        return need_sticks

    # return a list of digits that this digit can be transformed to
    # @lru_cache(maxsize=None)
    def can_transform_to(digit):
        psbl_num_costs = [] # from big to small
        for num in reversed(range(10)):
            target_digit = num_to_digit[num]
            cost = cost_to_transform(digit, target_digit)
            if cost == -1:
                continue
            psbl_num_costs.append((num, cost))
        return psbl_num_costs

    digit_transforms = [can_transform_to(digit) for digit in digits]
    min_cost_from = [0] * (n+1) # inclusive
    max_cost_from = [0] * (n+1) # inclusive
    for i in reversed(range(n)):
        # this digit min cost
        min_cost = min(cost for num, cost in digit_transforms[i])
        max_cost = max(cost for num, cost in digit_transforms[i])
        min_cost_from[i] = min_cost + min_cost_from[i+1]
        max_cost_from[i] = max_cost + max_cost_from[i+1]

    ans =...