CodeForces

地址：http://codeforces.com/problemset/problem/455/A

Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.

Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it a_k) and delete it, at that all elements equal to a_k + 1and a_k - 1 also must be deleted from the sequence. That step brings a_k points to the player.

Alex is a perfectionist, so he decided to get as many points as possible. Help him.

Input

The first line contains integer n (1 ≤ n ≤ 10⁵) that shows how many numbers are in Alex's sequence.

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁵).

Output

Print a single integer — the maximum number of points that Alex can earn.

Examples

Input

2
1 2

Output

2

Input

3
1 2 3

Output

4

Input

9
1 2 1 3 2 2 2 2 3

Output

10

Note

Consider the third test example. At first step we need to choose any element equal to 2. After that step our sequence looks like this [2, 2, 2, 2]. Then we do 4 steps, on each step we choose any element equals to 2. In total we earn 10 points.

　　　 题意：删除ak,那么这个数组所有的ak+1,ak-1都被删除，同时得到ak分。求能得到的最大分数。

　　 　解析：对每个数进行了桶排序num。这样对后面的差大于1的数没有后效性。。从0位置开始向右消去，那么要消除一个数  i   ，如果i-1被消去，那么i自然也不存在，此时dp[i] = dp[i-1]，分数不变，因为i没得删。如果i-1没被删去，那么　dp[ i ] = dp[ i-2 ]+num[i]*i;

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll num[maxn];
ll dp[maxn];
int main()
{          
     ll n;
     cin>>n;
     int maxx=-1;
     int x;
     for(int i=1;i<=n;i++)    
     {
         cin>>x;
         num[x]++;
         if(maxx<x)
             maxx=x;
     }
    dp[1]=num[1];　　//初始dp[1]
    for(int i=1 ; i <= maxx;  i++ )
    {
        dp[i]=max(dp[i-1],dp[i-2]+num[i]*i);
    }
    cout<<dp[maxx]<<endl;
}