SIRO 챌린지

문제

당신은 친구 지로와 함께 프로그래밍 대회 여름 훈련 캠프에 참가하고 있다. 지로는 라멘 체인점 SIRO의 열성 팬이다. SIRO는 지점마다 고유한 맛의 라멘을 내놓기 때문에, 지로는 오늘 밤 되도록 많은 지점을 돌며 라멘을 먹고 싶어 한다. 그런데 내일 아침 일찍 훈련 세션에 참가해야 해서 시간이 넉넉하지 않다. 그래서 지로는 제한된 시간 안에 라멘을 먹으러 갈 수 있는 서로 다른 지점의 최대 개수를 구해 달라고 부탁했다.

도시에는 $1$ 번부터 $n$ 번까지 번호가 붙은 철도역이 $n$ 개 있다. 캠프 장소에서 가장 가까운 역은 $s$ 번이다. $m$ 개의 역 쌍이 철도로 직접 연결되어 있고, 역 $a_i$ 와 역 $b_i$ 사이는 양방향 모두 $c_i$ 분 만에 이동한다. 이 가운데 $l$ 개의 역 근처에 SIRO 지점이 있다. 한 역 근처에 있는 SIRO 지점은 많아야 하나이고, $s$ 번 역 근처에는 지점이 없다. 역 $j_i$ 근처의 지점에서 지로가 라멘을 먹는 데는 $e_i$ 분이 걸린다.

역과 그 근처 지점 사이를 오가는 시간은 무시할 만큼 짧다. 지로가 지점에서 라멘이 나오기를 기다리는 시간도 없다고 본다.

지로는 지금 역 $s$ 에 있고 $t$ 분 안에 그 역으로 돌아와야 한다. 지로가 맛볼 수 있는 서로 다른 SIRO 지점은 최대 몇 곳인가?

입력

입력은 여러 데이터 세트로 이루어진다. 데이터 세트의 개수는 $100$ 을 넘지 않는다. 각 데이터 세트의 형식은 다음과 같다.

n m l s t
a1 b1 c1
:
:
am bm cm
j1 e1
:
:
jl el

각 데이터 세트의 첫 줄에는 정수 다섯 개가 주어진다.

역의 개수 $n$
철도로 직접 연결된 역 쌍의 개수 $m$
SIRO 지점의 개수 $l$
출발 역의 번호 $s$
지로에게 주어진 제한 시간 $t$

이어지는 $m$ 개의 줄에는 각각 정수 세 개가 주어진다.

연결된 두 역 $a_i$ 와 $b_i$
두 역 사이를 이동하는 데 걸리는 시간 $c_i$

이어지는 $l$ 개의 줄에는 각각 정수 두 개가 주어진다.

SIRO 지점이 있는 역의 번호 $j_i$
지로가 그 지점에서 먹는 데 걸리는 시간 $e_i$

입력의 끝은 $0$ 다섯 개가 적힌 줄로 표시하며, 그 줄은 데이터 세트에 포함되지 않는다.

각 데이터 세트는 다음 조건을 만족한다.

$2 \le n \le 300$
$1 \le m \le 5000$
$1 \le l \le 16$
$1 \le s \le n$
$1 \le t \le 100000$
$1 \le a_i, b_i \le n$
$1 \le c_i \le 1000$
$1 \le j_i \le n$
$1 \le e_i \le 15$
$s \ne j_i$
$j_i$ 는 모두 서로 다르다.
$a_i \ne b_i$
$i \ne j$ 인 모든 쌍에 대해 $(a_i, b_i) \ne (a_j, b_j)$ 이고 $(a_i, b_i) \ne (b_j, a_j)$ 이다.

출발점 $s$ 에서 도달할 수 없는 역이 있을 수 있다.

출력

각 데이터 세트마다 제한 시간 안에 지로가 갈 수 있는 서로 다른 지점의 최대 개수를 한 줄에 하나씩 출력한다.