prithivMLmods/Coder-Stat

1 2 3 4<h1>錬金マスター</h1>5<p>6  あなたはついに魔法の釜、錬金釜を手に入れました。錬金釜に複数のアイテムを入れると、新しいア イテムを作ることができます。新しく作ったアイテムは、他のアイテムを作るために錬金釜へ入れることもできます。アイテムを作るために必要なアイテムのリストを記したものを錬金レシピと呼ぶことにします。以下の 3 つは錬金レシピの例です。7</p>8 9<ol>10     <li> 木片と糸でラケットができる。</li>11     <li> お米と水でおにぎりができる。</li>12     <li> ラケットとマイクとおにぎりでギターができる。</li>13</ol>14 15<p>16  アイテムはお金を使って手にいれることもできますが、錬金釜で作った方が安くすむ場合もあります。例えば、各アイテムの購入価格が以下のように与えられているとします。17</p>18 19<center>20<table border=1 cellpadding=8 cellspacing=2>21<tr><td width=140>アイテム名</td><td width=140> 購入価格(円)</td></tr>22<tr><td>   木片 </td><td>           3,000</td></tr>23<tr><td>   糸          </td><td>      800</td></tr>24<tr><td>   お米     </td><td>           36</td></tr>25<tr><td>   水    </td><td>              0</td></tr>26<tr><td>   ラケット </td><td>          5,000</td></tr>27<tr><td>   マイク  </td><td>          9,800</td></tr>28<tr><td>   おにぎり </td><td>            140</td></tr>29<tr><td>   ギター </td><td>          98,000</td></tr>30</tr>31</table>32<br/>33</center>34 35<p>36 ラケットは 5,000 円で購入できますが、木片と糸を購入して錬金すれば 3,800 円で手に入れられます。更に、錬金を重ねることによりとてもお得にアイテムを手に入れられます。図 1 は上記 3 つの錬金レシピ例を組み合わせたものです。ギターは 98,000 円で購入できますが、木片、糸、お米、水、マイクを購入して錬金すれば、たったの 13,636 円で手に入れられます。37</p>38<br><br>39<center>40<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_recipe">41<p>図 1</p>42</center>43<br><br>44 45<p>46 あなたは冒険を楽に進めるため、なるべく安く目的のアイテムを手に入れようと考えました。 アイテムのリスト、錬金レシピのリスト、指定されたアイテムを入力とし、指定されたアイテムを作るために必要な金額の最小値を出力するプログラムを作成して下さい。47</p>48 49<!--50<p>51 アイテムリストに含まれるアイテムの種類 <var>n</var> は 1 以上 100 以下の整数とし、各アイテムを購入する場合の値段 <var>p</var> は 0 以上 1000000 以下とします。アイテムの名前 <var>i</var> は 1 文字以上 100 文字以下のアルファベットからなる半角文字列です。錬金レシピの種類 <var>m</var> は 0 以上 100 以下の整数です。 1つの錬金レシピはアイテムの名前 <var>o</var>、それを作るために必要なアイテムの個数 <var>k</var> 、 <var>k</var> 個のアイテム名 <var>q</var> のリストによって与えられます。<var>k</var> は 100 以下とします。52</p>53-->54 55<p>56 各アイテムの数量に限りはないものとします。アイテムは複数のレシピに使われることがありますが、1 つのアイテムを作るためのレシピはたかだか 1 つです。また、あるアイテムを起点としてレシピをたどっていったとき、そのアイテムが再びレシピに現れることはありません。57</p>58 59<H2>Input</H2>60 61<p>62複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の形式で与えられます。63</p>64 65<pre>66<var>n</var>67<var>s<sub>1</sub></var> <var>p<sub>1</sub></var>68<var>s<sub>2</sub></var> <var>p<sub>2</sub></var>69:70<var>s<sub>n</sub></var> <var>p<sub>n</sub></var>71<var>m</var>72<var>o<sub>1</sub></var> <var>k<sub>1</sub></var> <var>q<sub>1</sub></var> <var>q<sub>2</sub></var> ... <var>q<sub>k<sub>1</sub></sub></var>73<var>o<sub>2</sub></var> <var>k<sub>2</sub></var> <var>q<sub>1</sub></var> <var>q<sub>2</sub></var> ... <var>q<sub>k<sub>2</sub></sub></var>74:75<var>o<sub>m</sub></var> <var>k<sub>m</sub></var> <var>q<sub>1</sub></var> <var>q<sub>2</sub></var> ... <var>q<sub>k<sub>m</sub></sub></var>76<var>t</var>77</pre>78 79<p>801 行目にリストに含まれるアイテムの種類数 <var>n</var> (1 &le; <var>n</var> &le; 100) が与えられます。続く <var>n</var> 行に <var>i</var> 番目のアイテムの名前 <var>s<sub>i</sub></var> (1 文字以上 100 文字以下のアルファベットからなる半角文字列) とそれを購入する場合の値段 <var>p<sub>i</sub></var> (0 &le; <var>p<sub>i</sub></var> &le; 1000000)が与えられます。81</p>82 83<p>84続く行に錬金レシピの数 <var>m</var> (0 &le; <var>m</var> &le; 100) が与えられます。続く <var>m</var> 行に <var>i</var> 番目のレシピの情報が与えられます。各レシピとして、アイテムの名前 <var>o<sub>i</sub></var>、それを作るために必要なアイテムの個数 <var>k<sub>i</sub></var> (1 &le; <var>k<sub>i</sub></var> &le; 100) 、 <var>k<sub>i</sub></var> 個のアイテム名 <var>q<sub>1</sub></var>, <var>q<sub>2</sub></var> ... <var>q<sub>k<sub>i</sub></var> が与えられます。85</p>86 87<p>88最後の行に指定されたアイテム名 <var>t</var> が与えられます。89</p>90 91<p>92データセットの数は 30 を超えません。93</p>94 95<H2>Output</H2>96 97<p>98入力データセットごとに、最小の値段を１行に出力します。99</p>100 101<H2>Sample Input</H2>102 103<pre>1048105wood 3000106string 800107rice 36108water 0109racket 5000110microphone 9800111onigiri 140112guitar 980001133114racket 2 wood string115onigiri 2 rice water116guitar 3 racket microphone onigiri117guitar1181119computer 3000001200121computer1220123</pre>124 125<H2>Output for the Sample Input</H2>126 127<pre>12813636129300000130</pre>131 132 133 134