<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>

from collections import Counter
class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        hmap = Counter(power)
        power = sorted(hmap.keys())
        n = len(power)

        @cache
        def backtracking(curr):
            if curr >= n:
                return 0
            
            curr_val, res = power[curr], float('-inf')
            for i in range(1, 6):
                if curr + i < n and power[curr + i] > curr_val + 2:
                    res = max(res, backtracking(curr + i))
            return max(0, res) + curr_val * hmap[curr_val]

        return max([backtracking(i) for i in range(3)])


        @cache
        def backtracking(curr):
            curr_val, next_idx = power[curr], curr + 1
            
            # We skip the values close
            while next_idx < n and power[next_idx] <= curr_val + 2:
                next_idx += 1
            # If we are at the end, we return the value
            if next_idx == n:
                return hmap[power[curr]] * curr_val

            new_val, res = power[next_idx], float('-inf')
            while next_idx < n and power[next_idx] <= new_val + 2:
                res = max(res, backtracking(next_idx))
                next_idx += 1

            return res + hmap[power[curr]] * curr_val

        ans, next_idx = float('-inf'), 0
        while next_idx < n and power[next_idx] <= power[0] + 2:
            ans = max(ans, backtracking(next_idx))
            next_idx += 1
        return ans
216533