1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
import java.util.*;

/**
 * Created by wardziniak on 11/24/16.
 */
public class grz {

    public static void main(String[] args) {
        solution();
    }

    public static void solution() {
        final Scanner sc = new Scanner(System.in);
        int numberOfGlades = sc.nextInt();
        Glade[] glades = new Glade[numberOfGlades];

        for (int i = 0; i < numberOfGlades; i++) {
            glades[i] = new Glade(sc.nextLong(), sc.nextLong(), i);
        }

        Arrays.sort(glades);
        for (int i = 0; i < glades.length; i++)
            glades[i].orderBasedOnGrowNumber = glades.length-1-i;

        Arrays.asList(glades);
        TreeSet<Glade> chosenGlades = new TreeSet<>();
        TreeSet<Glade> nDayGlades = new TreeSet<>(new NdayComparator());
        for (Glade g: glades)
            g.setDay(0);
        nDayGlades.addAll(Arrays.asList(glades));
        long result;
        for (int i = 0; i < numberOfGlades; i++) {
            Glade chosen = nDayGlades.pollFirst();
            chosenGlades.add(chosen);
            int counter = i;
            result = 0;
            for (Glade g: chosenGlades) {
                result += g.numberOfMushroomAdDay(counter);
                counter--;
            }
            if (i < numberOfGlades -1) {
                TreeSet<Glade> tmp = new  TreeSet<>(new NdayComparator());
                for (Glade g: nDayGlades) {
                    g.addOffset(chosen.orderBasedOnGrowNumber);
                    g.setDay(i + 1);
                }
                tmp.addAll(nDayGlades);
                nDayGlades = tmp;
            }
            System.out.println(result);
        }
    }

    static class NdayComparator implements Comparator<Glade> {

        @Override
        public int compare(Glade t1, Glade t2) {
            if (t1.numberOfMushroomsAtCurrentDay() != t2.numberOfMushroomsAtCurrentDay())
                return t1.numberOfMushroomsAtCurrentDay() < t2.numberOfMushroomsAtCurrentDay() ? 1 : -1;
            if (t1.numberOfGrowingMushrooms != t2.numberOfGrowingMushrooms)
                return t1.numberOfGrowingMushrooms < t2.numberOfGrowingMushrooms ? 1 : -1;
            return t1.index < t2.index ? -1 : 1;
        }
    }

    static class Glade implements Comparable<Glade> {
        long startingNumberOfMushrooms;
        long numberOfGrowingMushrooms;
        int index;
        long currentDayNumberOfMushrooms;
        int orderBasedOnGrowNumber;
        int offsetOfDay = 0;

        Glade(long numberOfGrowingMushrooms, long startingNumberOfMushrooms, int index) {
            this.index = index;
            this.numberOfGrowingMushrooms = numberOfGrowingMushrooms;
            this.startingNumberOfMushrooms = startingNumberOfMushrooms;
        }

        public void setDay(int n) {
            currentDayNumberOfMushrooms = startingNumberOfMushrooms + (n - offsetOfDay) * numberOfGrowingMushrooms;
        }

        public long numberOfMushroomAdDay(int n) {
            return startingNumberOfMushrooms + n * numberOfGrowingMushrooms;
        }

        public long numberOfMushroomsAtCurrentDay() {
            return currentDayNumberOfMushrooms;
        }

        @Override
        public int compareTo(Glade other) {
            if (this.numberOfGrowingMushrooms != other.numberOfGrowingMushrooms)
                return this.numberOfGrowingMushrooms < other.numberOfGrowingMushrooms ? 1 : -1;
            return this.index - other.index;
        }

        public void addOffset(int orderBasedOnGrowNumber) {
            if (this.orderBasedOnGrowNumber < orderBasedOnGrowNumber)
                offsetOfDay++;
        }
    }
}