<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:
        count = collections.Counter(power)
        powerlist = list(set(power))
        powerlist.sort()
        def maxDamage(powerpart):
            n = len(powerpart)
            if n == 1:
                return powerpart[0][0]*powerpart[0][1]
            elif n == 2:
                return max(powerpart[0][0]*powerpart[0][1], powerpart[1][0]*powerpart[1][1])
            dp = [0]*(n+1)
            dp[-2] = powerpart[-1][0]*powerpart[-1][1]
            dp[-3] = max(powerpart[-1][0]*powerpart[-1][1], powerpart[-2][0]*powerpart[-2][1])
            for i in range(2, n):
                dp[-i-2] = max(dp[-i-1], dp[-i], powerpart[-i-1][0]*powerpart[-i-1][1]+dp[-i+1])

            return dp[0]
        n = len(powerlist)
        if n == 1:
            return sum(power)
        res = 0
        powerpart = [(powerlist[0], count[powerlist[0]])]
        last = powerlist[0]
        for i in range(1,n):
            if powerlist[i] - last == 1:
                powerpart.append((powerlist[i], count[powerlist[i]]))
                last = powerlist[i]
            elif powerlist[i] - last == 2:
                powerpart.append((powerlist[i]-1, 0))
                powerpart.append((powerlist[i], count[powerlist[i]]))
                last = powerlist[i]
            else:
                #print(powerpart, maxDamage(powerpart))
                res += maxDamage(powerpart)
                powerpart = [(powerlist[i], count[powerlist[i]])]
                last = powerlist[i]
        res += maxDamage(powerpart)
        return res

38766