[백준] 2109번 순회강연 (gold 3

import java.io.*;
import java.util.*;

class Point{
    int day;
    int v;
    public Point(int day, int v){
        this.day=day;
        this.v=v;
    }
}
public class Main{
    static int[] num;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n=Integer.valueOf(br.readLine());

        num=new int[10001];
        for(int i=1; i<10001; i++){
            num[i]=i;
        }

        PriorityQueue<Point> que=new PriorityQueue<>(new Comparator<Point>(){
            public int compare(Point o1, Point o2){
                if(o1.v==o2.v){
                    return -(o1.day-o2.day);
                }
                return -(o1.v-o2.v);
            }
        });


        for(int i=0; i<n; i++){
            st=new StringTokenizer(br.readLine());
            int p=Integer.valueOf(st.nextToken());
            int day=Integer.valueOf(st.nextToken());

            que.offer(new Point(day,p));
        }

        int sum=0;
        while(!que.isEmpty()){
            Point temp=que.poll();
            int t=Find(temp.day);
            if(t==0){
                continue;
            }
            sum+=temp.v;

            Union(t, t-1);
        }

        System.out.println(sum);


    }

    public static int Find(int a){
        if(a==num[a]){
            return a;
        }
        else{
            return num[a]=Find(num[a]);
        }
    }

    public static void Union(int a, int b){
        int fa=Find(a);
        int fb=Find(b);

        if(fa!=fb){
            if(fa<fb){
                num[fb]=fa;
            }
            else if(fa>fb){
                num[fa]=fb;
            }
        }
    }
}


//골드2의 공항, 컵라면과 비슷한 문제