훈련

면접 대비

시간 제한1초메모리 제한1024 MB

요약

각 훈련 상황에서 훈련을 최소 하나씩 골라 총 시간이 M시간을 넘지 않으면서 최대가 되는 값을 구합니다. 조건을 만족하는 계획이 없으면 -1을 출력합니다.

문제

작전과장 승서는 부대의 24-1분기 훈련 계획을 구성해야 한다. 이를 위해 승서는 훈련 계획에 넣을 훈련을 고른다.

훈련은 $N$ 가지 훈련 상황으로 분류되어 있으며, $i$ 번째 훈련 상황은 $d_i$ 개의 훈련으로 이루어져 있다. $i$ 번째 훈련 상황의 $j$ 번째 훈련에 걸리는 시간은 $t_{ij}$ 이다.

승서는 모든 상황에 대비가 완벽하기를 바란다. 그래서 각 훈련 상황에서 훈련을 최소 하나 골라 계획에 넣어야 한다. 또한 계획에 포함된 훈련들의 시간 합은 $M$ 시간을 넘을 수 없고, 각 훈련은 한 번만 진행할 수 있다.

위 조건을 지키면서 훈련 시간의 합이 최대가 되도록 계획을 짜려고 한다. 조건을 만족하는 최대 훈련 시간을 구하라.

첫 번째 줄에 훈련 상황의 가짓수 $N$ 과 최대 훈련 시간 $M$ 이 공백으로 구분되어 주어진다.

두 번째 줄에 각 훈련 상황에 속한 훈련의 개수 $d_1, \cdots, d_N$ 이 공백으로 구분되어 주어진다.

이후 $N$ 개의 줄에 걸쳐 $i+2$ 번째 줄에는 $i$ 번째 훈련 상황의 훈련 소요 시간 $t_{i1}, \cdots, t_{id_i}$ 가 공백으로 구분되어 주어진다.

조건을 만족하는 최대 훈련 시간을 출력한다.

각 훈련 상황에서 훈련을 하나 이상 고르는 것이 불가능하면 -1을 출력한다.

예제 2

입력

5 24
5 2 4 1 3
23 7 11 3 2
8 10
5 17 20 9
13
1 24 3

예상 출력

-1