<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:
        powerFreqs = Counter(power)
        power = sorted(list(set(power)))

        @cache
        def dp(i):
            if i < 0:
                return 0

            currPower = power[i] * powerFreqs[power[i]] 

            if i == 0:
                return currPower

            resultWithIdx = currPower
            resultWithoutIdx = dp(i - 1)
            
            if power[i - 1] < power[i] - 2:
                resultWithIdx += dp(i - 1)
            else:
                if power[i - 2] < power[i] - 2:
                    resultWithIdx += dp(i - 2)
                else:
                    resultWithIdx += dp(i - 3)
            
            return max(resultWithIdx, resultWithoutIdx)
        
        # return dp(len(power) - 1)

        prev3 = power[0] * powerFreqs[power[0]]
        
        if len(power) == 1:
            return prev3

        prev2 = 0

        if power[0] >= power[1] - 2:
            prev2 = max(prev3, power[1] * powerFreqs[power[1]])
        else:
            prev2 = prev3 + power[1] * powerFreqs[power[1]]
        
        if len(power) == 2:
            return prev2

        prev1 = 0
        prev1WithIdx = power[2] * powerFreqs[power[2]]
        if power[1] < power[2] - 2:
            prev1WithIdx += prev2
        else:
            if power[0] < power[2] - 2:
                prev1WithIdx += prev3
        
        prev1 = max(prev1WithIdx, prev2)

        if len(power) == 3:
            return prev1
        




        for i in range(3, len(power)):
            currPower = power[i] * powerFreqs[power[i]]

            resultWithIdx = currPower
            resultWithoutIdx = prev1
            
            if power[i - 1] < power[i] - 2:
                resultWithIdx += prev1
            else:
                if power[i - 2] < power[i] - 2:
                    resultWithIdx += prev2
                else:
                    resultWithIdx += prev3
            
            currIdxResult = max(resultWithIdx, resultWithoutIdx)

            prev1, prev2, prev3 = currIdxResult, prev1, prev2
        
        return prev1
        
78826