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

"""
___
Goal:
___

return max possible total damage magician can cast

___
Examples:
___

Input: power = [1,1,3,4]
Output: 6

Input: power = [7,1,6,6]
Output: 13

___
Assumptions:
___

1. casting power[i], then cannot cast any spell that has:
    - damage equal to:
        - power[i] - 2
        - power[i] - 1
        - power[i] + 1
        - power[i] + 2

2. each spell can be cast only once

3. 1 <= power <= 10^5
    - linearithmic solution is an upper bound
        - O(len(power)log(len(power)))

4. 1 <= power[i] <= 10^9

5. power is not sorted

___
Algorithms:
___


Algo 1: sort + Dynamic Programming
T: O(len(power)*log(len(power)) + len(power))


f(i) = sum(all i in power) + max(f(i - 1), f(i - 2), f(i - 4), f(i - 5))

base case = sum all min(power) for 4 smallest values possible


"""


class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        
        freq = {}
        memo = {}

        for p in power:
            freq[p] = freq.get(p, 0) + 1

        power = sorted(list(freq.keys()))

        
        def dfs(index: int) -> int:
            if index >= len(power):
                return 0
            elif index in memo:
                return memo[index]

            skip_value = dfs(index + 1)

            target_index = bisect_left(power, power[index] + 2 + 1)
            take_value = (freq[power[index]] * power[index] + dfs(target_index))
            memo[index] = max(take_value, skip_value)
            
            return memo[index]
        
        
        return dfs(0)
178976