00:00:00

Description

Editorial

Collect and Discard

MEDIUM10 pts

You are given an array of positive integers representing point values of collectible items. Your objective is to maximize the total points gathered by strategically selecting items from this collection.

When you select an item with value v, you immediately earn v points. However, the selection comes with a consequence: all items with values v - 1 and v + 1 are immediately removed from the collection (they become unavailable for future selection). This simulates a competitive or conflict-based point collection scenario where choosing one type of item excludes its immediate numerical neighbors.

You may perform this selection operation as many times as you wish, as long as there are items remaining in the collection. Each item can only be selected (and earn points) once. The challenge lies in determining which items to select to maximize the total accumulated points.

Return the maximum total points you can accumulate by optimally performing the selection operations.

Example

Input

nums = [3,4,2]

Output

6

Explanation

One optimal strategy:

Select the item with value 4, earning 4 points. This causes all items with values 3 and 5 to be discarded. Remaining items: [2].
Select the item with value 2, earning 2 points. Remaining items: []. Total points earned: 4 + 2 = 6.

Example

Input

nums = [2,2,3,3,3,4]

Output

9

Explanation

One optimal strategy:

Select an item with value 3, earning 3 points. This discards all items with values 2 and 4. Remaining items: [3,3].
Select another item with value 3, earning 3 points. Remaining items: [3].
Select the last item with value 3, earning 3 points. Remaining items: []. Total points earned: 3 + 3 + 3 = 9.

Example

Input

nums = [5]

Output

5

Explanation

With only a single item in the collection, select it to earn 5 points.

Accepted0/0·0% Acceptance

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

nums =

[3,4,2]

Loading problem...

101

00:00:00

Description

Editorial

Collect and Discard

MEDIUM10 pts

Return the maximum total points you can accumulate by optimally performing the selection operations.

Example

Input

nums = [3,4,2]

Output

6

Explanation

One optimal strategy:

Select the item with value 4, earning 4 points. This causes all items with values 3 and 5 to be discarded. Remaining items: [2].
Select the item with value 2, earning 2 points. Remaining items: []. Total points earned: 4 + 2 = 6.

Example

Input

nums = [2,2,3,3,3,4]

Output

9

Explanation

One optimal strategy:

Select an item with value 3, earning 3 points. This discards all items with values 2 and 4. Remaining items: [3,3].
Select another item with value 3, earning 3 points. Remaining items: [3].
Select the last item with value 3, earning 3 points. Remaining items: []. Total points earned: 3 + 3 + 3 = 9.

Example

Input

nums = [5]

Output

5

Explanation

With only a single item in the collection, select it to earn 5 points.

Accepted0/0·0% Acceptance

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

nums =

[3,4,2]

Collect and Discard

Hints

Collect and Discard

Hints