A shop has n candies on sale, with each candy having its own price. How many candies can you buy if you have x amount of money?
The number of candies is at most 10^5, and each price as well as x is in the range 1 \dots 10^9. The goal is an algorithm with time complexity O(n) or O(n \log n).
In a file candies.py, implement a function solve that returns the maximum number of candies you can buy.
def solve(prices, x):
# TODO
if __name__ == "__main__":
print(solve([1, 1, 1, 1], 2)) # 2
print(solve([2, 5, 3, 2, 8, 7], 10)) # 3
print(solve([2, 3, 4, 5], 1)) # 0
print(solve([2, 3, 4, 5], 10**9)) # 4
print(solve([10**9, 1, 10**9], 10**6)) # 1
Explanation: In the first example, you can buy any two candies. In the second example, you can buy three candies, for example the first three candies on the list. In the third example, you can buy no candies, since every candy costs more than 1.