Under construction

Still being built. Things may change

Distance Statistics

Time limit1sMemory limit1024 MB

Summary
Given a road network and an integer K, count the unordered pairs of distinct farms whose shortest path distance is at most K.
Level

Medium4 of 10

Topics
Graph, Shortest path
Solved
No attempts yet

Problem

Frustrated by how many distance queries it takes to find a reasonable route for his cow marathon, FJ decides to ask queries that tell him more. He supplies an integer K (1 ≤ K ≤ 1,000,000,000) and wants to know how many pairs of farms are at a distance of at most K from each other. Distance is the length of road required to travel from one farm to another. Count only pairs of distinct farms. For example, the pair (farm #5, farm #5) is not counted.

Input

  • Line 1: Two space-separated integers: N and M
  • Lines 2..M+1: Each line contains four space-separated entities, F1, F2, L, and D, that describe a road. F1 and F2 are the numbers of the two farms connected by the road, L is its length, and D is a character that is either 'N', 'E', 'S', or 'W', giving the direction of the road from F1 to F2.
  • Line M+2: A single integer, K.

Output

  • Line 1: The number of pairs of farms that are at a distance of at most K from each other.

Hint

There are 5 roads with length smaller than or equal to 10: 1-4 (3), 4-7 (2), 1-7 (5), 3-5 (7), and 3-6 (9).

Examples1

  1. Example 1

    Input
    7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
10
    Expected output
    5