You are an adventurer on a mystical journey, carrying a pouch filled with energy stones. These stones are given as an integer array stones, where stones[i] represents the energy stored in the i-th stone.
You begin your quest with a certain amount of energy, represented by the integer power, and a reputation score of 0.
Your objective is to maximize your reputation by using each stone in one of the following two ways (each stone may be used only once):
1. Activate a Stone (Face-Up)
If your current energy is at least stones[i], you may activate the stone in face-up mode.
-
You lose stones[i] energy.
-
You gain 1 reputation.
2. Trade a Stone (Face-Down)
If your current reputation is at least 1, you may trade the stone in face-down mode.
-
You gain stones[i] energy.
-
You lose 1 reputation.
Your goal is to determine the maximum reputation you can achieve after using any number of stones in any order.
Print the maximum reputation you can obtain.
The second line contains N space-separated integers, representing the values in the list stones.
The third line contains an integer representing your power (initial energy).
1
100
50
Output:
0
Explanation:
tokens = [100], power = 50
Since your reputation is 0 initially, you cannot play the stone face-down. You also cannot play it face-up since your power (50) is less than stones[0] (100).
Input:
2
200 100
150
Output:
1
Explanation:
Play stones[1] (100) face-up, reducing your power to 50 and increasing your reputation to 1.
There is no need to play stone 0, since you cannot play it face-up to add to your reputation. The maximum reputation achievable is 1.
Input
4
100 200 300 400
200
Output
2
Explanation
Play the stones in this order to get a score of 2:
Play stone 0 (100) face-up, reducing power to 100 and increasing reputation to 1.
Play stone 3 (400) face-down, increasing power to 500 and reducing reputation to 0.
Play stone 1 (200) face-up, reducing power to 300 and increasing reputation to 1.
Play stone 2 (300) face-up, reducing power to 0 and increasing reputation to 2.
The maximum reputation achievable is 2.