class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        if(nums.size() == 1) return nums[0];
        unordered_map<int,int> cnt;
        int n = nums.size();
        for(int i=0;i<n;i++){
            cnt[nums[i]]++;
        }
        vector<int>f(10001,0);
        int res = 0;
        f[0] = 0;
        for(int i=1;i<10001;i++){
            f[i] = cnt[i]*i;
            if(i>=2 && cnt.count(i)) f[i] = max(f[i-1],f[i-2]+cnt[i]*i);
            res = max(res,f[i]);
        }
        return res;
   }
};