31933번 - 나는 연어입니다

문제

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

$i$번째 강의 최소 폭은 $l_{i}$이고 최대 폭은 $r_{i}$이다. 만약 강의 최대 폭보다 연어의 크기가 크다면 이 강을 통과할 수 없고, 강의 최소 폭보다 작다면 강의 물살을 이기지 못할 것이다. 다시 말해, $i$번 강을 통과하는 연어는 $l_{i}$보다 크거나 같고 $r_{i}$보다 작거나 같은 크기를 가지고 있어야 한다.

1ドル$번 마을에서 출발하여 $N$번 마을에 도착할 수 있는 연어들의 수를 구해보자.

입력

첫 번째 줄에 연어들이 사는 마을의 수 $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$번 마을에 도착할 수 있는 연어들의 수를 출력한다.

제한

힌트