Karkit

Kaupassa on myytävänä $n$ karkkia, joilla jokaisella on tietty hinta. Montako karkkia voit ostaa enintään, kun sinulla on rahaa $x$?

Karkkien määrä on enintään $10^5$, ja jokaisen karkin hinta ja $x$ on välillä $1 \dots 10^9$. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$ tai $O(n \log n)$.

Toteuta tiedostoon candies.py funktio solve, joka ilmoittaa, montako karkkia voit ostaa enintään.

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

Selitys: Ensimmäisessä esimerkissä voit ostaa mitkä tahansa kaksi karkkia. Toisessa esimerkissä voit ostaa kolme karkkia, esimerkiksi listan kolme ensimmäistä karkkia, jotka maksavat yhteensä $10$. Kolmannessa esimerkissä et voi ostaa mitään karkkia, koska jokainen maksaa enemmän kuin $1$.