{"problem":{"name":"Road to Millionaire","description":{"content":"To become a millionaire, M-kun has decided to make money by trading in the next $N$ days. Currently, he has $1000$ yen and no stocks - only one kind of stock is issued in the country where he lives. H","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"m_solutions2020_d"},"statements":[{"statement_type":"Markdown","content":"To become a millionaire, M-kun has decided to make money by trading in the next $N$ days. Currently, he has $1000$ yen and no stocks - only one kind of stock is issued in the country where he lives.\nHe is famous across the country for his ability to foresee the future. He already knows that the price of one stock in the next $N$ days will be as follows:\n\n*   $A_1$ yen on the $1$\\-st day, $A_2$ yen on the $2$\\-nd day, ..., $A_N$ yen on the $N$\\-th day.\n\nIn the $i$\\-th day, M-kun can make the following trade **any number of times** (possibly zero), **within the amount of money and stocks that he has at the time**.\n\n*   Buy stock: Pay $A_i$ yen and receive one stock.\n*   Sell stock: Sell one stock for $A_i$ yen.\n\nWhat is the maximum possible amount of money that M-kun can have in the end by trading optimally?\n\n## Constraints\n\n*   $2 \\leq N \\leq 80$\n*   $100 \\leq A_i \\leq 200$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"m_solutions2020_d","tags":[],"sample_group":[["7\n100 130 130 130 115 115 150","1685\n\nIn this sample input, M-kun has seven days of trading. One way to have $1685$ yen in the end is as follows:\n\n*   Initially, he has $1000$ yen and no stocks.\n*   Day $1$: Buy $10$ stocks for $1000$ yen. Now he has $0$ yen.\n*   Day $2$: Sell $7$ stocks for $910$ yen. Now he has $910$ yen.\n*   Day $3$: Sell $3$ stocks for $390$ yen. Now he has $1300$ yen.\n*   Day $4$: Do nothing.\n*   Day $5$: Buy $1$ stock for $115$ yen. Now he has $1185$ yen.\n*   Day $6$: Buy $10$ stocks for $1150$ yen. Now he has $35$ yen.\n*   Day $7$: Sell $11$ stocks for $1650$ yen. Now he has $1685$ yen.\n\nThere is no way to have $1686$ yen or more in the end, so the answer is $1685$."],["6\n200 180 160 140 120 100","1000\n\nIn this sample input, it is optimal to do nothing throughout the six days, after which we will have $1000$ yen."],["2\n157 193","1216\n\nIn this sample input, it is optimal to buy $6$ stocks in Day $1$ and sell them in Day $2$, after which we will have $1216$ yen."]],"created_at":"2026-03-03 11:01:14"}}