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.
Author: HE, Zhuobin
Source: ZOJ Monthly, June 2008