Robots working
There are
n robots in the factory. Different robots are from different generations, and therefore, require different time to create the same product. New ones are faster, while older ones are slower. All the robots can work simultaneously. The factory needs to make X products. You are the manager of the factory, and the factory staff asks you to find the shortest time it would take to create those X products.Input
The first line of the input contains two integers
n (1 ≤ n ≤ ) and X (1 ≤ X ≤ ).The next line contains
n integers separated by a space representing the time required for each robot to create a product (1 ≤ ≤ ).Output
The program should print the minimum required time to make
X products.Examples
Input | Output |
3 8
4 2 5 | 10 |
Explanation
- The first machine will make 2 products (time=8), the second one will make 5 products (time=10), and the third one will make 1 product (time=5) ⇒ 10 products in total.
- The first machine will make 2 products (time=8), the second one will make 4 products (time=8), and the third one will make 2 products (time=10) ⇒ 10 products in total.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB