<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:
        max_power = -math.inf
        record = collections.defaultdict(int)
        for number in power:
            record[number] += number
            max_power = max(max_power, number)
        record[0] = 0
        uniques = list(set(power))
        uniques.sort()

        def calculating(index, record, memo, uniques):
            print(index)
            if index <0:
                return 0
            if index == 0:
                return record[uniques[0]]
            if index in memo:
                return memo[index]
            
            power_so_far = record[uniques[index]]
            i = index
            while uniques[i] >= uniques[index] - 2:
                if i >= 0:
                    i -= 1
                else:
                    break
            power_so_far += calculating(i, record, memo, uniques)
            if index - 1 >=0 :
                if uniques[index - 1] == uniques[index] - 1 or uniques[index - 1] == uniques[index] - 2:
                    power_so_far = max(power_so_far, calculating(index - 1, record, memo, uniques))
            if index -2 >= 0:
                if uniques[index - 2] == uniques[index] - 2:
                    power_so_far = max(power_so_far, calculating(index - 2, record, memo, uniques))
            # best_power = max(power_so_far, calculating(index - 1, record, memo, uniques), calculating(index - 2, record, memo, uniques))
            memo[index] = power_so_far
            return power_so_far

        memo = {}
        return calculating(len(uniques) - 1, record, memo, uniques)















        # def adding_power(spell_power, record, tracker):
        #     print(spell_power)
        #     if spell_power < 0:
        #         # print("----1------")
        #         return 0
        #     if spell_power in tracker:
        #         # print("----2------")
        #         return tracker[spell_power]
        #     if spell_power not in record:
        #         # print("----3------")
        #         new_spell_power = spell_power
        #         while new_spell_power not in record:
        #             new_spell_power -= 1
        #         # print(new_spell_power)
        #         best_power = adding_power(new_spell_power, record, tracker)
        #         for i in range(new_spell_power + 1, spell_power + 1):
        #             tracker[i] = best_power
        #         return best_power
            
        #     power_so_far = (record[spell_power] + adding_power(spell_power -3, record, tracker))
        #     best_power = max(power_so_far, adding_power(spell_power-1, record, tracker), adding_power(spell_power - 2, record, tracker))
        #     tracker[spell_power] = best_power
        #     return best_power
        
        # tracker = {}
        # return adding_power(max_power, record, tracker)

        
58796