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

    • Buying books

    There are n books in the store. You know the prices and the number of pages for each of the books. You have x dollars in your pocket, so you can’t spend more than x. What is the maximum number of pages you can buy? Note that you can buy each book only once.

    Input

    The first line of the input contains two integers n (1 ≤ n ≤ 100) and x (1 ≤ x ≤ ).
    The next line contains n space-separated integers (1 ≤ ≤ 1000) the costs of each book.
    The third line contains n space-separated integers (1 ≤ ≤ 1000) the number of pages for each book.

    Output

    The program should print the maximum number of pages you can buy with x.

    Examples

    Input
    Output
    4 10 4 8 5 3 5 12 8 1
    13

    Explanation

    You can buy the first and the third books. The cost will be 4 + 5 = 9, while the number of pages will be 5 + 8 = 13.
     

    Constraints

    Time limit: 3.5 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

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