Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3003
Technology Research

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Tom is fond of PC games, and recently, he love to play the game Civilization IV very much. However, one thing trouble him very much. that's the technology research system is very complicated, and he is asking you for help.

The research system is as follow:
1. All the technology in the game make up into a technology tree.
2. One technology can be research only when at least one of its directly precondition technology is researched.
3. Every technology need some tech-point to research. And every unit of time, we can offer V point basically. And if we had research k precondition technology (including the indirectly ones), we will have k point additionally.
    e.g. In the following sample, if we had research ACE. When we research D, we can offer V+2 point per time unit benefit from AC, E doesn't make contribute for F hadn't been researched.

Tom now give you the description of the technology tree, and need you to find the minimum time to research the technology he wants.


The input contains multiple test case.
In each case, the first line contain two integers N (1<=N<=1000) and V(1<=V<=100), N is the technology in the research system.
Then the following N lines there a string and a integer (<=2000) each which indicating the name of the technology and the tech-point it need.
The following N-1 line contain two string each. the first string represent the precondition technology, and the second string represent the new technology.
At last, there is the names of technology he wants.
There is a blank line between each test case.


Output the minimum time to finish researching the technology. The answer must be rounded to two decimal places.

Sample Input

3 1
a 1
b 1
c 7
a c
b c

Sample Output


Author: HE, Zhuobin
Source: ZOJ Monthly, June 2008
Submit    Status