This page is still under construction.

Parts of this page are still being built. What you see may change.

Clay Shooting Game

Interview

Time limit1sMemory limit1024 MB

Summary
Choose an order to hit the N clays; hitting clay i in round j scores b[i]*j, but once a path is used no clay returns to it, so timing must be respected.
Level

Medium7 of 10

Topics
Dynamic programming, Bit manipulation, Greedy, Sorting
Solved
No attempts yet

Problem

Clay shooting is a game in which you shoot down incoming clays with a gun. The rules are as follows.

  • Clays fly from the right side of the screen to the left, and you score by shooting a clay at the moment it passes the center of its path and knocking it down.
  • There are N paths for the clays, numbered 1 through N from the one closest to the bottom of the screen.
  • The gun fires from the bottom center of the screen. The bullet immediately hits and knocks down the nearest clay on a path, but it cannot pass through a clay.
  • The game is played in rounds. The first round is round 1 and the last round is round N.
  • Let path i be the path of the i-th clay from the bottom of the screen. A clay traveling along each path passes the center of the screen every a[i] seconds after a round starts.
  • Hitting a clay starts the next round. However, on the path of the clay hit in the previous round, no clay passes any more even after the round is reset.
  • If the clay hit in round j was traveling along the i-th path from the bottom of the screen, the score gained this time is b[i] × j.
  • The game ends when there are no more clays to hit.

Jinjeong wants to know the highest score he can get by playing the game. Help Jinjeong.

Input

The first line gives the number of paths N that the clays travel along.

The next N lines each give a pair of integers (a[i], b[i]). For the path that is the i-th closest to the bottom of the screen, a[i] is the interval at which a clay passes the center of the screen, and b[i] is the score for hitting that clay.

Output

Print the maximum score that can be obtained.

Constraints

1 ≤ N ≤ 16

1 ≤ a[i] ≤ 100

1 ≤ b[i] ≤ 100

Examples4

  1. Example 1

    Input
    4
2 4
4 2
6 8
8 6
    Expected output
    58

  2. Example 2

    Input
    16
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
    Expected output
    1496

  3. Example 3

    Input
    16
2 100
3 99
5 98
7 97
11 96
13 95
17 94
19 93
23 92
29 91
31 90
37 89
41 88
43 87
47 86
53 85
    Expected output
    12920

  4. Example 4

    Input
    5
17 1
23 2
17 2
23 3
17 1
    Expected output
    31