<p>You are given an integer array <code>rewardValues</code> of length <code>n</code>, representing the values of rewards.</p>

<p>Initially, your total reward <code>x</code> is 0, and all indices are <strong>unmarked</strong>. You are allowed to perform the following operation <strong>any</strong> number of times:</p>

<ul>
	<li>Choose an <strong>unmarked</strong> index <code>i</code> from the range <code>[0, n - 1]</code>.</li>
	<li>If <code>rewardValues[i]</code> is <strong>greater</strong> than your current total reward <code>x</code>, then add <code>rewardValues[i]</code> to <code>x</code> (i.e., <code>x = x + rewardValues[i]</code>), and <strong>mark</strong> the index <code>i</code>.</li>
</ul>

<p>Return an integer denoting the <strong>maximum </strong><em>total reward</em> you can collect by performing the operations optimally.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">rewardValues = [1,1,3,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p>During the operations, we can choose to mark the indices 0 and 2 in order, and the total reward will be 4, which is the maximum.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">rewardValues = [1,6,4,3,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">11</span></p>

<p><strong>Explanation:</strong></p>

<p>Mark the indices 0, 2, and 1 in order. The total reward will then be 11, which is the maximum.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rewardValues.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= rewardValues[i] &lt;= 5 * 10<sup>4</sup></code></li>
</ul>


def helper(rewardValues, rightPos, rewardCeiling):
    """
    rewardValues: the rewardValues array
    rightPos: starting position
    rewardCeiling: no matter how we mark elements from rewardValues[:rightPos], their sum must <= this number
    
    We start from end of array (i.e. always try to mark the larger numbers first)
    
    Return the maximum reward we can get from rewardValues[:rightPos], that maximum reward should be <= rewardCeiling 
    """
    res = 0
    # For every number, we try to either mark it or not
    for i in reversed(range(rightPos)):
        # Current val exceeds the limit, can't be marked, skip
        if rewardValues[i] > rewardCeiling:
            continue

        # If we mark current reward
        # Then the new rewardCeiling is limited by 2 conditions
        # 1. it has to be smaller than allocation left (rewardCeiling - rewardValues[i])
        # 2. it has to be smaller than current reward (rewardValues[i] - 1)
        newRewardCeiling = min(rewardCeiling - rewardValues[i], rewardValues[i] - 1)
        # Skip if even we met the ceiling (taking max possible rewards), and we still can't improve result
        if newRewardCeiling + rewardValues[i] <= res:
            break
        
        res = max(res, rewardValues[i] + helper(rewardValues, i, newRewardCeiling))

    return res

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        # Remove duplicate (since we won't be able to pick same number twice)
        # and sort in ascending order
        rewardValues = sorted(list(set(rewardValues)))
        N = len(rewardValues)
        lastReward = rewardValues[-1]

        return lastReward + helper(rewardValues, N-1, lastReward - 1)
24200