TV 시청

면접 대비

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

요약

정해진 날짜에 열리는 파티마다 특정 드라마가 논의될 때, 밥이 파티가 없는 날 하루 최대 10시간씩만 시청해 모든 드라마를 제때 끝낼 수 있는지 판정한다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 구간, 구현
정답자: 아직 제출이 없습니다

문제

Bob의 친구들은 TV 시리즈를 좋아해서 자기 생일 파티에서 그 이야기를 하곤 한다. Bob은 친구들과 같은 시리즈를 보지 않았다는 이유로 자주 소외감을 느낀다.

Bob은 특정 날짜에 열리는 파티에 초대받았고, 그 파티에 모두 참석하려고 한다. 그는 각 파티에서 어떤 TV 시리즈가 논의될지 알고 있으며, 친구들과 그 시리즈에 대해 이야기하려면 해당 시리즈를 다 봐 두어야 한다. Bob은 하루에 10시간을 초과해서 TV를 보고 싶지 않고, 파티가 있는 날에는 TV를 볼 시간이 없다.

그는 TV 시리즈를 언제든지 멈추고 나중에 이어서 볼 수 있지만, 어떤 시리즈가 논의되는 파티에 갈 때는 그 시리즈를 전부 다 본 상태여야 한다. Bob이 이것을 해낼 수 있을까?

입력

첫째 줄에 파티의 수 $n$ 과 TV 시리즈의 수 $k$ 가 주어진다 ( $1 \leq n,k \leq 2 \times 10^5$ ). TV 시리즈는 $1$ 부터 $k$ 까지 번호가 매겨져 있다.

다음 줄에 $k$ 개의 정수가 주어지며, $i$ 번째 정수는 TV 시리즈 $i$ 의 길이를 시간 단위로 나타낸다. 어떤 시리즈도 $10^6$ 시간보다 길지 않다.

다음 $n$ 개의 줄은 파티를 순서대로 설명한다. $i$ 번째 줄은 두 정수 $1 \leq d\_i \leq 2 \times 10^5$ 와 $c\_i \geq 1$ 로 시작하며, 각각 파티가 열리는 날짜와 그 파티에서 논의될 TV 시리즈의 수이다. 이어서 같은 줄에 $c\_i$ 개의 서로 다른 정수가 주어지며, 이는 파티에서 논의될 TV 시리즈들이다. 모든 $c\_i$ 의 합은 $2 \times 10^5$ 보다 크지 않다.

Bob은 어느 날에도 파티에 두 개 이상 초대받지 않았다. 지금은 $0$ 일 아침이며, 따라서 Bob은 오늘 파티에 가지 않는다.

출력

TV 시리즈가 논의되는 행사에 맞춰 해당 시리즈를 전부 볼 수 있으면 Ja를 출력한다. 불가능하면 Nej를 출력한다.

예제3

예제 1
입력
```
3 4
3 20 5 5
2 1 2
4 2 3 4
6 2 1 2
```
예상 출력
```
Ja
```
예제 2
입력
```
2 4
7 3 8 3
1 2 1 2
2 3 2 3 4
```
예상 출력
```
Nej
```

예제 3

입력

3 5
3 10 4 8 15
2 2 1 3
4 1 2
7 3 5 4 2

예상 출력

Ja