• 아이템들이 그룹단위로 묶여있는 냅색 문제의 변형이다.
• 그룹단위 냅색에서 가장 흔한 유형은 각 그룹에서 0~1개 또는 1개의 아이템을 고르도록 주어지는 문제들이다. 그 외에, 각 그룹에서 0개 이상의 아이템을 고를 수 있는 문제가 있을수 있는데, 이 경우는 그룹이 없을때와 차이가 없어진다. 그냥 전체 아이템에 대해서 0-1 냅색을 돌리는것과 같다.
• 이 문제에서는 그룹별로 1개 이상의 아이템을 고르게 되어있다. 이것을 풀기 위해서는 각 그룹마다 그룹의 아이템들을 가지고 0-1 냅색을 돌려서 0개 이상의 아이템을 골라서 나올수 있는 값들을 테이블에 저장하되, 0개의 아이템을 골랐을때만 나올수 있는 값들은 테이블에 저장되지 않아야 한다. 즉, 1개 이상의 아이템을 추가해서 나온 값들에 대해서만 구분이 가능해야 한다.
• 한가지 방법은, 만들어진 값들마다 가장 나중에 추가된 그룹 번호를 붙여주는 것이다. i번 그룹까지의 아이템들을 사용해서 만들어진 테이블이 있다면, 거기에 저장된 값들의 번호는 0~i의 값을 가질것이다. i+1번째 그룹의 아이템들을 사용해서 테이블을 갱신할때에는 번호가 i 또는 i+1인 값들에 대해서만 갱신해주면 된다. (공식 해설의 풀이)
• 다른 방법은, 그냥 i+1번 그룹을 처리한 결과를 저장하기 위한 새로운 테이블을 만들고, j번째 아이템을 사용해서 테이블을 갱신할때에는, i+1번째 테이블에 i번째 테이블의 값들에 j번 아이템을 추가해서 나온 값들과 i+1번째 테이블의 값들에 j번 아이템을 추가해서 나온 값들을 함께 저장해주는 것이다.
• 테이블을 새로 만들 필요가 없는 첫번째 방법이 더 간단해보이지만, 이 방법은 값에 번호를 매핑하는 테이블이 하나 더 필요한 대신, 두번째 방법은 그것이 필요 없다는 장점이 있다. 그래서, 가능한 값들 중에서 가장 XX한 값을 구해야 하는 문제가 아니라, 그냥 가능한 값의 목록만 필요한 문제에서는 두번째 방법을 사용할 경우 여전히 값마다 가능,불가능의 불리언 상태만 저장해주면 충분하기 때문에 비트셋을 이용해서 최적화가 가능하다는 장점이 있다.
• 이 문제 역시 그냥 가능한 값의 목록만 필요하기 때문에, 두번째 방법을 이용할 경우 비트셋 최적화가 가능하고, 첫번째 방법에 비해서 훨씬 빠르게 풀 수 있다. 첫번째 방법으로는 (코드1) 약 800ms, 두번째 방법 (코드2) 으로는 56ms가 걸렸다

"""Solution code for "BOJ 31265. 훈련".

- Problem link: https://www.acmicpc.net/problem/31265
- Solution link: http://www.teferi.net/ps/problems/boj/31265

Tags: [knapsack]
"""

import sys


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    # pylint: disable=unused-variable
    d = [int(x) for x in sys.stdin.readline().split()]
    t = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    dp = [-2] * (M + 1)
    dp[0] = -1
    for i, t_i in enumerate(t):
        for t_ij in t_i:
            for v in range(M, -1, -1):
                if v >= t_ij and dp[v - t_ij] >= i - 1:
                    dp[v] = i

    print(next((v for v in range(M, -1, -1) if dp[v] == N - 1), -1))


if __name__ == '__main__':
    main()

"""Solution code for "BOJ 31265. 훈련".

- Problem link: https://www.acmicpc.net/problem/31265
- Solution link: http://www.teferi.net/ps/problems/boj/31265

Tags: [knapsack]
"""

import sys


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    # pylint: disable=unused-variable
    d = [int(x) for x in sys.stdin.readline().split()]
    t = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]

    mask = (1 << (M + 1)) - 1
    dp_cur = 0b1
    for t_i in t:
        dp_prev, dp_cur = dp_cur, 0b0
        for t_ij in t_i:
            dp_cur |= ((dp_cur << t_ij) | (dp_prev << t_ij)) & mask

    print(dp_cur.bit_length() - 1 if dp_cur != 0 else '-1')


if __name__ == '__main__':
    main()