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