A survey network has n beacons (numbered 0 to n-1) linked by one-way cables. Each cable carries a signal from its start beacon to its end beacon at a positive integer cost.

Starting from beacon s, a beacon is said to be within budget if the minimum total cost to reach it from s is at most B. The source s itself is within budget (its cost is 0, and B >= 0). Count how many beacons are within budget.

Input format

Line 1: four integers n, m, s, and B. Each of the next m lines: three integers u v w, a one-way cable from beacon u to beacon v with cost w.

Output format

A single integer: the number of beacons (including s) whose shortest cost from s is at most B.

Constraints

• 1 <= n <= 100000
• 0 <= m <= 200000
• 0 <= s, u, v <= n-1
• 0 <= B <= 1000000000
• 1 <= w <= 1000000

4 4 0 4
0 1 2
1 2 2
0 3 10
2 3 1

3

3 1 0 3
0 1 5

1