## JDCC '17 Contest 3 S4 - Interview Dominance

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Justin is feeling assertive, and decides to give his interviewer a programming challenge! Justin places $$​(1 \le N \le 10^5)$$ cards on the table, with each card having a certain number on it.

Every turn, Justin removes a single card from the table, and he gains a number of points equal to the number on the card.

Assume the number on the card picked is ​. Then, all cards with the number and ​ are removed from the table (Justin gets no points for these cards).

The game ends once there are no more cards on the table.

Justin asks the interviewer what the maximum number of points he can earn is, and not knowing the answer, the interviewer asks you to help them!

#### Input

The first line contains an integer $$​(1 \le N​ \le 10^5)$$, representing the number of cards.

The next line has ​ integers $$(0 \le c​_n ​\le 10^5)$$, representing the number on the $$n​^{th}$$​ ​card.

For of points, $$N​ \le 100$$.

#### Output

Output the maximum number of points that one can get by playing the game optimally.

This value may not fit in a 32-bit integer, and may need to be stored in a Long or long long variable in Java/C++ respectively (Python users are fine).

#### Sample Input

7
1 4 2 3 5 4 3

#### Sample Output

12

#### Explanation for Sample Input

Justin plays the following moves:

• Remove the card (with value of ) and remove all cards with a value of or
• Remove the card (with value of ) and remove all cards with a value of or
• Remove the card (with value of ) and remove all cards with a value of or
• Remove the card (with value of ) and remove all cards with a value of or

There are no more cards left and Justin ends up with points in total.