Grand Prix engineers are tuning the boost pads embedded along a go-kart track. Each of the n pads has a fixed charge rating. A kart starts a lap with charge 0. Whenever the kart passes a pad it has not used yet, the driver may activate it, but only if the pad's rating is strictly greater than the kart's current charge at that moment; activating a pad adds its rating to the kart's charge. Each pad may be activated at most once, and the driver may visit the pads in whatever order they choose (skipping any pad is also allowed). Determine the highest final charge the driver can reach.
Print a single integer: the maximum charge the kart can end a lap with, over every valid choice and order of pad activations.
Example 1
Input
4 1 1 3 3
Expected
4
Explanation
Activate one pad rated 1 first (1 > 0, charge becomes 1), then a pad rated 3 (3 > 1, charge becomes 4). The remaining pads — the second 1 and second 3 — can no longer be activated, since neither 1 nor 3 is greater than the current charge of 4. The maximum final charge is 4.
Example 2
Input
5 1 6 4 3 2
Expected
11
Explanation
Activate pad 1 (1 > 0, charge becomes 1), then pad 4 (4 > 1, charge becomes 5), then pad 6 (6 > 5, charge becomes 11). Pads rated 2 and 3 are skipped entirely — fitting either of them into the sequence would break the strictly-greater-than rule at some point. The maximum final charge is 11.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →