나는 연어입니다

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

요약

각 강은 l부터 r까지 범위의 크기를 가진 연어만 지날 수 있습니다. 1번 마을에서 N번 마을까지 갈 수 있는 연어의 수를 구합니다.

난이도: 보통10점 중 6점
유형: 그래프, BFS, 이분 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

태초에 연어들은 $N$ 번 마을에서 태어났다. 오늘날 $K$ 마리의 연어가 모두 $1$ 번 마을에 살고 있고, 이들은 산란기를 맞아 $N$ 번 마을로 돌아가는 모험을 떠나려 한다. 마을은 총 $N$ 개이고, 이들을 잇는 강은 총 $M$ 개이다. 산란기의 연어는 강을 거슬러 올라갈 힘이 충분하므로 강을 어느 방향으로든 자유롭게 다닐 수 있다. 서로 다른 두 마을을 잇는 강은 최대 $1$ 개 존재한다.

입력

첫 번째 줄에 마을의 수 $N$ 과 강의 수 $M$ 이 공백으로 구분되어 주어진다. $(2\leq N \leq 5\,000;1\leq M\leq 5\,000)$ 두 번째 줄부터 $M$ 개의 줄에 걸쳐 각 줄마다 정수 $u$ , $v$ , $l$ , $r$ 이 공백으로 구분되어 주어진다. 이는 $u$ 번 마을과 $v$ 번 마을을 잇는 강의 최소 폭이 $l$ 이고 최대 폭이 $r$ 임을 뜻한다. $(1\leq u,v\leq N; u\neq v; 1\leq l \leq r \leq 10^{9})$ $M+2$ 번째 줄에는 $1$ 번 마을에 살고 있는 연어의 수 $K$ 가 주어진다. $(1\leq K \leq 500\,000)$ $M+3$ 번째 줄에는 $K$ 개의 정수가 공백으로 구분되어 주어지며, 이는 연어들의 크기이다. 각 연어의 크기는 $1$ 이상 $10^{9}$ 이하의 정수이다.

출력

$1$ 번 마을에서 출발하여 $N$ 번 마을에 도착할 수 있는 연어의 수를 출력한다.

예제1

예제 1

입력

6 10
1 2 2 7
1 3 1 8
2 3 2 4
2 4 5 6
4 6 5 8
3 6 2 3
3 5 1 1
5 6 1 4
2 6 7 11
3 4 4 9
10
10 9 5 5 6 4 1 1 2 3

예상 출력