Problem Statement 
 An old witch is making a love potion. She has a lot of recipes and each of them has the following form:
S=N_{1}S_{1}+?+N_{k}S_{k}
where N_{1}, ?, N_{k} are singledigit integers between 1 and 9, inclusive, S_{1}, ?, S_{k} are names of ingredients, k is an integer greater than or equal to 1, and S is name of the resulting potion (all names contain only uppercase letters). This means that if she mixes N_{1} units of S_{1}, ..., N_{k} units of S_{k} all together, she will obtain 1 unit of S. There may be multiple recipes for the same potion. In that case, the potion can be obtained using any one of them. The ingredients are also potions, and some of them can be bought at the market.
You want to create 1 unit of the potion called LOVE. You are given String[] recipes, each element of which is a recipe formatted as described above. You are also given a String[] marketGoods and a int[] cost. Each element of marketGoods is the name of a potion you can purchase at the market. The ith element of cost is the cost of 1 unit of the ith potion in marketGoods. Return the cheapest cost of obtaining 1 unit of LOVE. If this cost is greater than 1,000,000,000, return 1,000,000,001 instead. If the potion cannot be obtained, return 1 instead. 

Definition 
 Class:  MakingPotions  Method:  getCost  Parameters:  String[], int[], String[]  Returns:  int  Method signature:  int getCost(String[] marketGoods, int[] cost, String[] recipes)  (be sure your method is public) 




Constraints 
  marketGoods will contain between 1 and 50 elements, inclusive. 
  Each element of marketGoods will contain between 1 and 50 characters, inclusive. 
  Each element of marketGoods will contain only uppercase letters ('A''Z'). 
  All elements of marketGoods will be distinct. 
  cost will contain the same number of elements as marketGoods. 
  Each element of cost will be between 1 and 100, inclusive. 
  recipes will contain between 0 and 50 elements, inclusive. 
  Each element of recipes will contain between 4 and 50 characters, inclusive. 
  Each element of recipes will contain only uppercase letters ('A''Z'), nonzero digits ('1''9') and the characters '+' and '='. 
  Each element of recipes will be formatted as described in the problem statement. 

Examples 
0)  
 {"LOVE", "WATER", "HONEY"}  {100, 1, 30}  {"LOVE=5WATER+3HONEY"} 
 Returns: 95  The LOVE potion is sold at the market, but the witch can make it for a lower cost. 


1)  
 {"WATER", "HONEY", "HOP"}  {2, 6, 9}  {"LOVE=2WATER+4HONEY+2BEER", "BEER=1HOP+3WATER+1HOP"} 
 Returns: 76  To obtain LOVE, one must make two units of BEER at a cost of 24 each, and then mix 2 units of WATER, 4 units of HONEY and 2 units of BEER, which will cost a total of 76. 


2)  
 {"ORANGEJUICE", "APPLEJUICE"}  {6, 4}  {"JUICEMIX=1ORANGEJUICE+1APPLEJUICE"} 
 Returns: 1  The witch doesn't have a LOVE recipe.



3)  
 {"WATER", "HONEY", "HOP"}  {1,22,17}  {"LOVE=7WATER+3HONEY", "LOVE=2HONEY+2HOP"} 
 Returns: 73  The witch has two LOVE recipes and prefers the first one.



4)  
 {"OIL", "WATER"}  {60, 70}  {"FIRSTPOTION=1OIL+1SECONDPOTION", "SECONDPOTION=4WATER+1FIRSTPOTION", "LOVE=1FIRSTPOTION+1SECONDPOTION"} 
 Returns: 1  

5)  
 {"HONEYBIT"}
 {100}
 {"LOVE=6HONEYMEGABYTE","HONEYMEGABYTE=2HONEYFIFTYTWELVEKBYTES",
"HONEYFIFTYTWELVEKBYTES=8HONEYSIXTYFOURKBYTES","HONEYSIXTYFOURKBYTES=8HONEYEIGHTKBYTES",
"HONEYEIGHTKBYTES=8HONEYKBYTE","HONEYKBYTE=2EIGHTBYEIGHTWORDS","EIGHTBYEIGHTWORDS=8EIGHTWORDS",
"EIGHTWORDS=8HONEYWORD","HONEYWORD=8HONEYBYTE","HONEYBYTE=8HONEYBIT"}

 Returns: 1000000001  

6)  
 {"WATER"}  {1}  {"LOVE=1LOVE"} 
 Returns: 1  Some recipes can be useless. 


7)  
 {"MILK","WATER","HOP"}
 {6,1,14}  {"NECTAR=4HOP+2MILK","LOVE=5MILK+3BEER","LOVE=2WATER+1LOVE","LOVE=2MIX+1NECTAR",
"MIX=1MILK+1WATER+1HOP","BEER=5WATER+2HOP","LOVE=1NECTAR+3WATER+3HOP","NECTAR=3BEER+1MILK+2MILK"}

 Returns: 110  
