<p>A magician has various spells.</p>

<p>You are given an array <code>power</code>, where each element represents the damage of a spell. Multiple spells can have the same damage value.</p>

<p>It is a known fact that if a magician decides to cast a spell with a damage of <code>power[i]</code>, they <strong>cannot</strong> cast any spell with a damage of <code>power[i] - 2</code>, <code>power[i] - 1</code>, <code>power[i] + 1</code>, or <code>power[i] + 2</code>.</p>

<p>Each spell can be cast <strong>only once</strong>.</p>

<p>Return the <strong>maximum</strong> possible <em>total damage</em> that a magician can cast.</p>

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

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

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

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

<p>The maximum possible damage of 6 is produced by casting spells 0, 1, 3 with damage 1, 1, 4.</p>
</div>

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

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

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

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

<p>The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with damage 1, 6, 6.</p>
</div>

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

<ul>
	<li><code>1 &lt;= power.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= power[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:

        # we borrow some code from #3180:
        # ... and it times out.
        # we borrow code from #3181 instead:
        # ... and it times out.
        # let's try a completely different approach.

        power.sort()    # but don't make it unique using set() this time
        print(f'{len(power)=}')
        counts = Counter(power)
        power_pairs = sorted(counts.items())
        power_N = [N for (N, count) in power_pairs]
        power_count = [count for (N, count) in power_pairs]
        print(f'{len(power_N)    =}')
        print(f'{len(power_count)=}')

        # @cache    # must roll our own ignoring 'depth' parameter
        DP_cache = [None] * (len(power_N) + 1)
        def DP(orig_index: int, depth=0) -> int:

            index = orig_index
            
            margin = '  ' * depth

            answer = DP_cache[orig_index]
            if answer is not None:
                return answer

            if index >= len(power_N):
                answer = 0
                DP_cache[orig_index] = answer
                return answer

            # print(f'{margin}DP({orig_index})')
            take = 0
            N = power_N[index]
            try:
                # if you take one N, take them all
                # print(f'{margin}  take {N} * {power_count[index]} [{index}]')
                take += N * power_count[index]
                while power_N[index] == N:
                    # SHOULD only happen once
                    index += 1
                while power_N[index] <= N + 2:
                    # print(f'{margin}  -no- {power_N[index]} [{index}]')
                    index += 1
            except IndexError:
                pass
            take += DP(index, depth+1)
            # print(f'{margin}  {take=}')

            index = orig_index
            
            try:
                # if you skip one N, skip them all
                # print(f'{margin}  skip {N} [{index}]')
                while power_N[index] == N:
                    # SHOULD only happen once
                    index += 1
            except IndexError:
                pass
            skip = DP(index, depth+1)
            # print(f'{margin}  {skip=}')

            # print(f'{margin}  answer: {take=} {skip=}')
            answer = max(take, skip)
            DP_cache[orig_index] = answer
            return answer
        
        print(f'prime cache in reverse, from {len(power_N)} to {0}')
        for i in reversed(range(len(power_N))):
            # print(f'{i=} prime cache')
            ignore = DP(i)

        return DP(0)

83834