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

import functools

class Solution:
    def search_left(self, arr, val):
        # if insert the val into arr to keep it sorted,
        # return the left most index
        i, j = 0, len(arr) - 1
        while i + 1 < j:
            mid = (i + j) // 2
            target = arr[mid]
            if target == val:
                i, j = i, mid
                continue
            
            if target < val:
                i, j = mid, j
            else:
                i, j = i, mid
        
        if arr[i] >= val:
            return i
        # arr[i] < val
        if arr[j] >= val:
            return j
        # arr[j] < val
        return j + 1
            
            

    def maximumTotalDamage(self, _power: List[int]) -> int:
        power = sorted(_power)
        val_count = collections.Counter(power)
        
        @functools.lru_cache(None)
        def dp(i: int):
            if i == len(power):
                return 0
            
            # i <= len(power) - 1
            val = power[i]
            p = self.search_left(power, val + 3)

            return max(dp(p) + val_count[val] * val, dp(i + val_count[val]))
        return dp(0)
        
        # dp = [0 for _ in range(len(power) + 1)]

        # # init
        # dp[len(power)] = 0

        # # deduction
        # for i in range(len(power) - 1, -1, -1):
        #     val = power[i]
        #     p = self.search_left(power, val + 3)
        #     dp[i] = max(dp[p] + val_count[val] * val, dp[i + 1])
        # return dp[0]
214029