Role-Playing Game

Interview

Time limit2sMemory limit1024 MB

Summary

Pick tasks whose prerequisites are all done, keep total time within m minutes, maximize total experience, and print one valid completion order.

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

Problem

When Zhenya has free time, he likes to spend it on his favorite role-playing game. Of course, he has a dream: to reach level 255, which means collecting the experience points that level requires. Unfortunately, he does not have much free time, so he wants to use it as efficiently as possible. Help him.

Experience points come from completing tasks. Each task has the time it takes to complete, the number of experience points it gives, and a list of tasks that must be completed before it becomes available.

Find the maximum amount of experience Zhenya can gain in his free time.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 16$ , $1 \le m \le 1000$ ), the number of tasks and the number of free minutes Zhenya has. The next $n$ lines describe the tasks, one per line. Each line starts with three integers $t_i$ , $p_i$ , and $k_i$ ( $1 \le t_i, p_i \le 1000$ , $0 \le k_i < n$ ): the number of minutes task $i$ takes, the experience points it gives, and the number of tasks that must be completed before task $i$ . Then follow $k_i$ distinct integers from $1$ to $n$ , the numbers of those tasks.

Output

The first line contains a single integer, the maximum experience Zhenya can gain in his free time. The second line contains the numbers of the tasks he must complete to gain that much experience, in the order he must complete them.

Examples2

Example 1
Input
```
2 10
5 3 1 2
5 2 0
```
Expected output
```
5
2 1
```
Example 2
Input
```
3 9
4 1 0
5 2 1 1
6 3 1 1
```
Expected output
```
3
1 2
```