问题描述

你现在和你的朋友 Jiro 参加了编程竞赛夏季培训营，他是一位 SIRO 拉面连锁店的爱好者。由于每家 SIRO 餐厅都有自己独特的拉面口味，他想在晚上尽可能多地去不同的餐厅尝试。然而，他今晚时间有限，因为他明天早上要早起参加培训课程。所以他请你找出他在有限的时间内可以去吃拉面的不同餐厅的最大数量。

城市里有 $n$ 个火车站，编号从 $1$ 到 $n$。火车站 $s$ 是离培训营地最近的站点。有 $m$ 对火车站通过铁路直接连接着：你可以在 $c_i$ 分钟内往返于站点 $a_i$ 和 $b_i$ 之间。在这些站点中，有 $l$ 个附近有 SIRO 餐厅。每个站点周围最多只有一个 SIRO 餐厅，并且车站 $s$ 附近没有餐厅。Jiro 在离车站 $j_i$ 最近的餐厅吃拉面需要 $e_i$ 分钟。

往返于车站和附近的 SIRO 餐厅之间只需要很短的时间。你也可以假设 Jiro 在餐厅里不需要等待拉面上菜。

Jiro 现在在车站 $s$，他必须在 $t$ 分钟内回到这个车站。他最多可以品尝到多少家不同的 SIRO 餐厅呢？

输入

输入是一个数据集序列，数据集的数量不超过 $100$。每个数据集的格式如下：

$n$ $m$ $l$ $s$ $t$
$a_1$ $b_1$ $c_1$
:
:
$a_m$ $b_m$ $c_m$
$j_1$ $e_1$
:
:
$j_l$ $e_l$

每个数据集的第一行包含五个整数：

• $n$ 是车站的数量，

• $m$ 是直接连接的火车站对的数量，

• $l$ 是 SIRO 餐厅的数量，

• $s$ 是起点车站，以及

• $t$ 是 Jiro 的时间限制。

以下的 $m$ 行每行包含三个整数：

• $a_i$ 和 $b_i$ 是两个连接的车站，

• $c_i$ 是在这两个车站之间移动所需的时间。

以下的 $l$ 行每行包含两个整数：

• $j_i$ 是 SIRO 餐厅所在的车站，

• $e_i$ 是 Jiro 在餐厅吃饭所需的时间。

输入结束时有一行包含五个零，这行不包含在数据集中。

数据集满足以下约束：

• $2 \le n \le 300$

• $1 \le m \le 5{,}000$

• $1 \le l \le 16$

• $1 \le s \le n$

• $1 \le t \le 100{,}000$

• $1 \le a_i, b_i \le n$

• $1 \le c_i \le 1{,}000$

• $1 \le j_i \le n$

• $1 \le e_i \le 15$

• $s \ne j_i$

• $j_i$ 互不相同。

• $a_i \ne b_i$

• $(a_i, b_i) \ne (a_j, b_j)$ 以及 $(a_i, b_i) \ne (b_j, a_j)$ 对于任意的 $i \ne j$

注意，可能有一些车站从起点 $s$ 不可达。

输出

对于每个数据集，输出在时间限制内 Jiro 可以去的最大数量的 SIRO 餐厅。

示例输入

2 1 1 1 10
1 2 3
2 4
2 1 1 1 9
1 2 3
2 4
4 2 2 4 50
1 2 5
3 4 5
2 15
3 15
4 6 3 1 29
1 2 20
3 2 10
4 1 5
3 1 5
2 4 3
3 4 4
2 1
4 5
3 3
0 0 0 0 0```

### 示例输出

```plain
1
0
1
3```

* * *

### 来源

[JAG Practice Contest for ACM-ICPC Asia Regional 2013](http://acm-icpc.aitea.net/index.php?2013%2FPractice%2F%CC%CF%B5%BC%C3%CF%B6%E8%CD%BD%C1%AA)

* * *