Byte Coin

Interview

Time limit0.5sMemory limit512 MB

Summary

Given n up to 15 days of Byte Coin prices and initial cash W, buy and sell whole coins each day to maximize the cash held after selling everything on day n.

Level: Medium6 of 10
Topics: Dynamic programming, Brute force, Greedy, Implementation
Solved: No attempts yet

Problem

The International Capital Property Company (ICPC) is investing funds in Byte Coin. Byte Coin is a virtual currency created by Dr. Kim. In reality, the price of Byte Coin cannot be predicted, but in this problem we assume that the fluctuations of the Byte Coin price can be predicted exactly in advance.

We know in advance the fluctuations of Byte Coin over n days from day 1 to day n, as shown in Figure 1, and we are given an initial amount of cash W. The red squares in Figure 1 represent the Byte Coin price on each day. Suppose we can buy or sell Byte Coin every day. However, we cannot sell or buy a fraction of a single Byte Coin. We want to maximize the cash we hold when we sell all the coins we own on day n.

Figure 1. Graph of Byte Coin price fluctuations over 10 days

For example, suppose we know in advance the Byte Coin fluctuation graph shown in Figure 1 on the first day, and the initial cash given to us is 24. To maximize our profit, we can buy and sell Byte Coin as follows. On the first day, we spend 20 cash to buy 4 coins. On the second day, we sell all the coins to get 28 cash and have a total of 32 cash. On day 5, we spend 32 cash to buy 16 coins. On day 7, we sell all the coins and have a total of 128 cash. On day 9, we spend 126 cash to buy 42 coins, and on day 10 we sell all the coins. Then on day 10 the cash becomes 170, which is the maximum.

Given the number of days n, the initial cash W, and the Byte Coin price on each day from day 1 to day n, write a program that outputs the maximum final cash we will hold when we sell all the coins we own on day n.

Input

The input uses standard input. The first line gives a positive integer n, the number of days, and the initial cash W (1 ≤ n ≤ 15, 1 ≤ W ≤ 100,000). In the following n lines, the i-th line gives an integer si, the Byte Coin price on day i (1 ≤ si ≤ 50).

Output

The output uses standard output. Print on one line the maximum cash we hold when we sell all the coins we own on day n. Note that although the initial cash W is not that large, the final cash can become very large.

Examples3

Example 1
Input
```
10 24
5
7
5
4
2
7
8
5
3
4
```
Expected output
```
170
```
Example 2
Input
```
5 15
5
4
4
2
7
```
Expected output
```
50
```
Example 3
Input
```
7 54
7
5
5
4
2
2
1
```
Expected output
```
54
```