Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

    • 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

    1. 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.
    1. 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: 2 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue