<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 typing import List

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        n = len(power)
        power.sort()  # Sort powers in ascending order
        
        # Create spell list with (power, damage) tuples
        spells = [(power[0], power[0])]
        for i in range(1, n):
            if power[i] != power[i-1]:
                spells.append((power[i], power[i]))
            else:
                # Combine spells with same power
                spells[-1] = (spells[-1][0], spells[-1][1] + power[i])
        
        memo = [-1] * (len(spells) + 1)
        
        def binarySearch(target: int, start: int) -> int:
            left, right = start, len(spells)
            while left < right:
                mid = left + (right - left) // 2
                if spells[mid][0] > target + 2:
                    right = mid
                else:
                    left = mid + 1
            return left  # Return index of next valid spell
        
        def dfs(index: int) -> int:
            if index >= len(spells):
                return 0
            
            if memo[index] != -1:
                return memo[index]
            
            # Use current spell
            current_power, current_damage = spells[index]

            # Find next valid spell (power > current_power + 2) using binary search
            next_index = binarySearch(current_power, index + 1)

            use_current = current_damage + dfs(next_index)
            
            # Skip current spell
            skip_current = dfs(index + 1)
            
            # Return maximum damage between using and skipping current spell
            memo[index] = max(use_current, skip_current)

            return memo[index]
        
        return dfs(0)  # Start DFS from the first spell
133909