장로 스탄의 부탁

메이플 월드는 $N$ 개의 마을과 서로 다른 두 마을을 잇는 $M$ 개의 도로로 구성되어 있다. 모험가는 메이플 월드에 존재하는 $K$ 가지의 아이템을 적절히 수집해 모험을 해나가야 한다. 편의상 마을은 $1$부터 $N$까지, 도로는 $1$부터 $M$까지, 아이템은 $1$부터 $K$까지 번호가 매겨져 있다.

모험가는 헤네시스에서 장로 스탄에게 최대한 많은 마을에 방문하라는 퀘스트를 받았다. 헤네시스는 $1$번 마을이다.

지도를 살펴보니 각 마을을 잇는 도로마다 강력한 몬스터가 있어서, 몬스터를 물리치고, 아이템을 수집하게 된다.

$i$번 도로는 $U_i$번 마을과 $V_i$번 마을을 연결하며, $i$번 도로에 있는 몬스터를 물리치기 위해서는 $P_{i, 1}, \cdots, P_{i, C_i}$번 아이템을 모두 갖고 있어야 한다. 몬스터를 물리쳐야만 도로를 통해 이동할 수 있으며, $i$번 도로에 있는 몬스터를 물리치면 $W_i$번 아이템을 얻을 수 있다. 몬스터를 물리치더라도 아이템이 소모되지 않는다.

메이플 월드의 도로 정보가 주어지면 헤네시스에서 출발하여 방문할 수 있는 마을의 최대 개수를 구하는 프로그램을 작성하시오.

같은 마을을 여러 번 지날 수 있지만, 여러 번 지나더라도 한 번으로 세는 것에 유의하라.

입력 형식

첫 줄에 마을의 수 $N$, 도로의 수 $M$, 아이템의 종류 수 $K$, 모험가가 처음에 갖고 있는 아이템의 종류 수 $S$가 공백으로 구분되어 주어진다. ($2 \le N \le 200\,000;$ $1 \le M \le 200\,000;$ $1 \le S \le K \le 200\,000$)

그다음 줄에 모험가가 처음에 갖고 있는 아이템을 나타내는 $S$ 개의 서로 다른 정수 $A_1, A_2, \cdots, A_S$가 공백으로 구분되어 주어진다. ($1 \le A_i \le K$)

이어지는 $M$ 개의 줄의 $i$ 번째 줄에는 $i$번 도로에 대한 정보를 나타내는 네 정수 $U_i$, $V_i$, $W_i$, $C_i$와 함께 $C_i$ 개의 서로 다른 정수 $P_{i, 1}, \cdots, P_{i, C_i}$가 공백으로 구분되어 주어진다. ($1 \le U_i, V_i \le N;$ $U_i \ne V_i;$ $1 \le W_i \le K;$ $1 \le C_i \le K;$ $1 \le P_{i, j} \le K$)

서로 다른 두 마을을 잇는 도로는 최대 하나만 주어진다. 또한, 주어지는 $C_i$의 합은 $500\,000$을 넘지 않는다.

출력 형식

첫 줄에 방문할 수 있는 마을의 최대 수를 출력한다.

예제 1

5 6 7 1
1
1 2 2 1 1
2 3 3 1 1
3 4 4 1 5
4 1 5 1 4
2 4 6 2 1 3
4 5 7 1 7

4

예제 2

6 7 8 1
1
1 2 2 1 3
1 3 3 1 4
1 4 4 1 5
2 3 5 1 6
2 4 6 1 7
3 4 7 1 2
5 6 8 1 1

1

예제 3

7 8 5 2
5 1
1 2 2 1 1
2 3 4 5 2 3 5 1 4
1 4 1 2 2 5
2 5 3 1 3
3 6 4 4 2 1 5 4
4 5 5 3 1 2 5
5 6 5 1 1
7 6 3 5 1 2 3 4 5

5

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

해설