Delete and Earn

Difficulty: 1600 3000 ms 128 MB

dp

Choosing value v earns v × (its count), but deletes every occurrence of v−1 and v+1 from the pool. Repeat until empty. Maximize the total earned.

Input: the first line has N; the second line has N positive integers.

Output: the maximum total.

Constraints:

• 1 ≤ N ≤ 10⁵
• 1 ≤ a_i ≤ 10⁴

Sample Tests

3
3 4 2

6

5
2 2 3 3 3

9

Read the Editorial