LCC '21 Contest 2 S2 - Oscar's Bagels

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

Oscar is selling bagels at the school bake sale. He sells one bagel per minute, and can choose to stop selling at any point. He must sell one bagel per minute until he stops.

Oscar has N types of bagels, c_i of each type of bagel, and each has a sell value v_i based on the type of bagel. In addition, the bagels are worth more the later they are sold. Namely, a bagel is sold for t \times v_i coins on the t-th minute, starting from minute 1.

Since he is trying to earn the maximum profit, Oscar would like to know the most coins he can earn.

Input Specification

The first line of input will contain one integer N (1 \leq N \leq 10^4), the number of types of bagels Oscar has.

The next N lines will contain two space-separated integers, v_i (0 \leq v_i \leq 100), the value of the i-th type of bagel, and c_i (1 \leq c_i \leq 10^4) the number of the i-th type of bagel Oscar has.

Output Specification

Output a single value, the maximum amount of coins Oscar can earn.


Subtask 1 [20%]

N \leq 10^2

c_i \leq 10^2

Subtask 2 [80%]

No additional constraints.

Sample Input 1

0 1
100 1
5 1
6 2

Sample Output 1


Explanation for Sample 1

Oscar can sell the first bagel on minute 1, third bagel on minute 2, fourth bagel on minutes 3 to 4, and second bagel on minute 5, for a total revenue of 1 \times 0 + 2 \times 5 + 3 \times 6 + 4 \times 6 + 5 \times 100 = 552.

Sample Input 2

0 5
4 20
1 1

Sample Output 2



There are no comments at the moment.