Algorithm

B. Martian Dollar
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem Link- https://codeforces.com/problemset/problem/41/B
input
standard input
output
standard output

One day Vasya got hold of information on the Martian dollar course in bourles for the next n days. The buying prices and the selling prices for one dollar on day i are the same and are equal to ai. Vasya has b bourles. He can buy a certain number of dollars and then sell it no more than once in n days. According to Martian laws, one can buy only an integer number of dollars. Which maximal sum of money in bourles can Vasya get by the end of day n?

Input

The first line contains two integers n and b (1 ≤ n, b ≤ 2000) — the number of days and the initial number of money in bourles. The next line contains n integers ai (1 ≤ ai ≤ 2000) — the prices of Martian dollars.

Output

Print the single number — which maximal sum of money in bourles can Vasya get by the end of day n.

Examples
input
Copy
2 4
3 7
output
Copy
8
input
Copy
4 10
4 3 2 1
output
Copy
10
input
Copy
4 10
4 2 3 1
output
Copy
15



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <cstdio>
#include <vector>

int main(){

    int n, b; scanf("%d %d\n", &n, &b);
    std::vector<int> price(n);
    for(int p = 0; p < n; p++){scanf("%d\n", &price[p]);}

    int ans(b);
    for(int u = 0; u < n; u++){
        for(int v = u + 1; v < n; v++){
            int candidate = b - (b / price[u]) * price[u] + (b / price[u]) * price[v];
            if(candidate > ans){ans = candidate;}
        }
    }

    printf("%d\n", ans);

    return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2 4
3 7

Output

x
–
+
cmd
8
Advertisements

Demonstration

Codeforces Solution-B. Martian Dollar-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+