31265번 - 훈련 서브태스크

문제

작전과장 승서는 부대의 24-1분기 훈련 계획을 구성하여야 한다. 이를 위해 승서는 훈련 계획에 포함할 훈련들을 선정해야 한다.

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

승서는 모든 상황에 대해 완벽한 대비를 하고 싶기 때문에 각 훈련 상황에서 적어도 하나의 훈련을 골라 훈련 계획에 넣으려고 한다. 또한, 훈련 계획에 포함된 훈련들의 시간 총합은 $M$시간을 초과할 수 없으며 각 훈련은 한 번만 진행할 수 있다.

완벽한 전투대비태세 유지를 위해, 승서는 위 조건 아래에서 훈련 시간의 총합이 최대가 되도록 훈련 계획을 구성하고자 한다. 조건을 만족하는 최대 훈련 시간을 구해 국군 장병들의 완벽한 전투대비태세 유지를 도와주자.

입력

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

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

이후 $N$개의 줄에 걸쳐 $i+2$번째 줄에 $i$번째 훈련 상황에 속한 훈련의 소요 시간을 나타내는 $d_i$개의 정수 $t_{ij}$가 공백으로 구분되어 주어진다.

출력

조건을 만족하는 최대 훈련 시간을 구하여라.

만약 각 훈련 상황에서 적어도 하나의 훈련을 골라 훈련 계획에 넣는 것이 불가능하다면 -1을 출력한다.

제한

• 1ドル \le N \le 1,000円$
• 1ドル \le M \le 10,000円$
• 1ドル \le d_i \le 1,000円$; $\sum\limits_{i=1}^N d_i \le 1,000円$
• 1ドル \le t_{ij} \le 1,000円$
• 모든 입력은 정수이다.

서브태스크

힌트