Maximize Money Earned from Spare Parts

Problem Statement

Maximize Money Earned from Spare Parts Description A mechanic can buy spare parts from a manufacturer. There are n parts, numbered 0 to n-1 . Buying part i costs cost[i] , and fitting it earns the mechanic 2^i . The mechanic has x in hand. Each part may be bought at most once, and the parts bought must cost at most x in total. Choose the parts that maximise the total earnings. Because the total can be enormous, report it modulo 10^9 + 7 . Complete the function findMaximumMoneyEarned in the editor below. Input The input is read from standard input as whitespace-separated integers, in this order: n , the number of parts. n integers, the array cost . x , the money available. Output Print a single integer: the maximum earnings, reduced modulo 10^9 + 7 . Examples Example 1 Input: 5 10 20 14 40 50 70 Output: 20 Explanation: Parts 2 and 4 cost 14 + 50 = 64 , which fits in 70 , and earn 2^2 + 2^4 = 4 + 16 = 20 . Parts 0 , 1 and 2 cost 44 but earn only 1 + 2 + 4 = 7 . Parts 1 and 4 cost 70 and