Task Scheduling with Dependencies and a Time Limit

Alice has a set of tasks that she needs to complete, each with an associated processing time. However, some tasks depend on the completion of other tasks. Given the tasks and their dependencies, determine whether it is possible for Alice to complete all tasks sequentially within a given time limit.

Each task is described by three (or more) integers:
(t_i): the time required to complete the task,
(d_i): a unique identifier for the task, and
(k_i): the number of dependencies that the task has. This is followed by (k_i) integers, each representing a task that must be completed before the current task can start.

Tasks must be performed in an order that respects the dependencies. More formally, if we denote a valid ordering of tasks as (T_1, T_2, \ldots, T_n), then for every task (T_j) that depends on task (T_i), it must hold that (i < j). Also note that tasks are executed sequentially so the total completion time is the sum of the processing times in the order they are done.

The total processing time, (\sum t_i), must not exceed the given time limit (L) and the dependency constraints must be satisfied. Return "YES" if this is possible, and "NO" otherwise.

inputFormat

The input is read from standard input (stdin) and has the following format:

The first line contains two integers (n) and (L), where (n) is the number of tasks and (L) is the maximum allowed total time.

This is followed by (n) lines, each describing a task. Each task line contains:

(t_i) (d_i) (k_i) [(dep_1) (dep_2) ... (dep_{k_i})]

where (t_i) is the processing time, (d_i) is the unique task identifier, (k_i) is the number of dependencies, and the next (k_i) integers are the identifiers of tasks that must be completed before this task.

outputFormat

Print a single line to standard output (stdout) containing either "YES" if it is possible to complete all tasks within the time limit while satisfying the dependency constraints, or "NO" otherwise.## sample

4 10
3 0 0
2 1 0
4 2 1 0
1 3 2 1 2

YES