535. Delete and Earn

0

Medium

Given an array of integers called 'nums', the goal is to maximize the total number of points earned by performing the following operation any number of times:
- Select any element 'nums[i]' and delete it to earn 'nums[i]' points.
- After deleting 'nums[i]', all elements equal to 'nums[i] - 1' and 'nums[i] + 1' must also be deleted.
Find the maximum number of points that can be earned by applying the above operation some number of times.

Input Format

The first line of input contains an integer 'N', representing the size of the array.
The second line contains 'N' space-separated integers, representing the elements of the array.

Output Format

Print the maximum number of points that can be earned.

Example

Input

6
2 2 3 3 3 4

Output

9

Constraints

1 <= n <= 10^4
1 <= nums[i] <= 10^4

Loading...

View Submissions

Console