LCC '21 Contest 2 S2 - Oscar's Bagels

View as PDF

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

Author:
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 types of bagels, of each type of bagel, and each has a sell value based on the type of bagel. In addition, the bagels are worth more the later they are sold. Namely, a bagel is sold for coins on the -th minute, starting from minute .

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 , the number of types of bagels Oscar has.

The next lines will contain two space-separated integers, , the value of the -th type of bagel, and the number of the -th type of bagel Oscar has.

Output Specification

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

Sample Input 1

4
0 1
100 1
5 1
6 2

Sample Output 1

552

Explanation for Sample 1

Oscar can sell the first bagel on minute , third bagel on minute , fourth bagel on minutes to , and second bagel on minute , for a total revenue of .

Sample Input 2

3
0 5
4 20
1 1

Sample Output 2

1326