Training

Interview

Time limit1sMemory limit1024 MB

Summary

Pick at least one training from each situation so the total time stays within M hours and is as large as possible. Print -1 if no valid plan exists.

Level: Medium5 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Operations section chief Seungseo must plan the unit's training for the first quarter of 24. To do so, Seungseo selects which trainings to include in the plan.

Trainings are grouped into $N$ training situations, and the $i$ -th situation consists of $d_i$ trainings. The $j$ -th training in the $i$ -th situation takes $t_{ij}$ hours.

Seungseo wants to be fully prepared for every situation. So the plan must include at least one training from each situation. The total time of the trainings in the plan cannot exceed $M$ hours, and each training can be carried out only once.

Under these conditions, find the maximum total training time that the plan can have.

Input

The first line contains the number of training situations $N$ and the maximum training time $M$ , separated by a space.

The second line contains $N$ integers $d_1, \cdots, d_N$ , the number of trainings in each situation, separated by spaces.

The next $N$ lines, starting from line $i+2$ , contain the times of the trainings in the $i$ -th situation. Line $i+2$ holds $d_i$ integers $t_{i1}, \cdots, t_{id_i}$ , separated by spaces.

Output

Print the maximum total training time that satisfies the conditions.

If it is impossible to pick at least one training from every situation, print -1.

Constraints

$1 \le N \le 1000$
$1 \le M \le 10000$
$1 \le d_i \le 1000$ ; $\sum_{i=1}^N d_i \le 1000$
$1 \le t_{ij} \le 1000$
All input values are integers.

Examples2

Example 1
Input
```
2 7
2 1
4 3
2
```
Expected output
```
6
```

Example 2

Input

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

Expected output

-1