Let's go on an adventure

Hanshin lost the vote for his party's top seat, took the blame, and gave up his seat in the assembly. Then he left for the east coast of the United States to find a new kind of fun. A friend who lives in Virginia lent him a car, but the tank holds a limited amount of fuel, so he planned a trip around Virginia that stays inside the distance he can drive.

The friend told him what every region is worth. Hanshin wants a route from the start to the destination that makes the total value of the regions he passes through as large as possible, without running out of fuel.

The trip is only for fun, so he may pass through the same city more than once. A region adds its value the first time he passes through it and adds nothing after that. The start and the destination both count toward the total.

The first line has $c$, the number of regions he can visit. Each of the next $c$ lines has the name of a region and the value of that region, separated by a space.

The next line has $m$, the number of roads between regions. Each of the next $m$ lines has the names of the two regions a road connects and the length of that road. Road lengths are integers and every road can be driven in both directions. Two regions may be joined by more than one road, and a road may start and end at the same region.

The next line has $p$, the number of test cases. Each of the next $p$ lines has a start, a destination, and the maximum distance he can drive.

Every value is separated by spaces and no region name contains a space. A name written as Virginia Beach never appears in the input.

• $1 \le c \le 11$
• each region name is a string of $1$ to $20$ letters and digits, and all names are distinct
• each region value is an integer between $-1000$ and $1000$
• $0 \le m \le 100$
• each road length is an integer between $1$ and $10000$
• $1 \le p \le 10$
• the maximum distance is an integer between $0$ and $1000000$
• the start and the destination are region names given above, and they may be the same

For each test case print one line in the form Case x: v, where $x$ is the case number starting from $1$ and $v$ is the largest total value he can collect. The total includes the start and the destination.

If no route from the start to the destination fits inside the maximum distance, print Not possible in place of $v$.