Java program for the above approach
import java . util . ArrayList ; import java . util . Arrays ; import java . util . PriorityQueue ; class GFG { static class Pair implements Comparable < Pair > { int first , second ; public Pair ( int first , int second ) { this . first = first ; this . second = second ; } @ Override public int compareTo ( GFG . Pair o ) { if ( this . first == o . first ) { return this . second - o . second ; } return this . first - o . first ; } } static final int MAXX = 10000 , INF = ( int ) 1e9 ;