1. If time limit exceeded, use a better sorting algorithm. In my case, insertion sort spent barely over a second, while merge sort spent only 0.6 of a second.

2. used long long. Also, before multiplying a long long and an int together, convert the int first.

Sorting the input is a waste of time, quite frankly. Try some of your own inputs, the solution can be very simple & fast.