Dont use System.out.println(ans); instead use PrintWriter for output stream or alternatively you can also use stringBuilder to  append all your answer and finally print your StringBuilder

Maybe your sort is the issue. See https://codeforces.com/blog/entry/7108

In the second submission, your issue is Arrays.sort, and the infamous Quicksort TLE that can result from specially generated input. These are the Java sorting functions I use.

public static void sort(int[] arr) {
	Random rgen = new Random();
	for (int i = 0; i < arr.length; i++) {
		int r = rgen.nextInt(arr.length);
		int temp = arr[i];
		arr[i] = arr[r];
		arr[r] = temp;
	}
	Arrays.sort(arr);
}

public static void sort(long[] arr) {
	Random rgen = new Random();
	for (int i = 0; i < arr.length; i++) {
		int r = rgen.nextInt(arr.length);
		long temp = arr[i];
		arr[i] = arr[r];
		arr[r] = temp;
	}
	Arrays.sort(arr);
}

//Sort an array (immune to quicksort TLE)
public static void sort(int[][] arr) {
	Random rgen = new Random();
	for (int i = 0; i < arr.length; i++) {
		int r = rgen.nextInt(arr.length);
		int[] temp = arr[i];
		arr[i] = arr[r];
		arr[r] = temp;
	}
	Arrays.sort(arr, new Comparator<int[]>() {
		@Override
		public int compare(int[] a, int[] b) {
			return a[0]-b[0];
		}
	});
}

public static void sort(long[][] arr) {
	Random rgen = new Random();
	for (int i = 0; i < arr.length; i++) {
		int r = rgen.nextInt(arr.length);
		long[] temp = arr[i];
		arr[i] = arr[r];
		arr[r] = temp;
	}
	Arrays.sort(arr, new Comparator<long[]>() {
		@Override
		public int compare(long[] a, long[] b) {
			if (a[0] > b[0])
				return 1;
			else if (a[0] < b[0])
				return -1;
			else
				return 0;
			//Ascending order.
		}
	});
}