시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB158806447.407%

문제

클레이 사격 게임은 날아오는 클레이들을 총으로 맞춰 떨어트리는 게임이다. 게임의 룰은 다음과 같다.

  • 클레이 게임은 화면 우측에서 좌측을 향해 날아오는 클레이가 경로상의 가운데를 지나가는 타이밍에 맞춰 총을 쏘아 클레이를 맞춰 떨어트리면서 점수를 얻는 게임이다.
  • 클레이가 날아오는 경로는 화면 아래에 가까운 순서대로 1번 경로로부터 N번 경로까지 총 N개의 경로가 존재한다.
  • 총은 화면 아래 정중앙에서 발사되며, 발사된 총알은 즉시 경로상의 가장 가까운 클레이를 맞춰 떨어트리나 클레이를 관통하지는 못한다.
  • 게임은 라운드 방식으로 최초 라운드는 1번 라운드이며 마지막 라운드는 N번 라운드이다.
  • 화면 아래에서 i번째로 가까운 클레이의 경로를 i번 경로라고 하면 각 경로를 지나가는 클레이는 라운드 시작 후 a[i]초마다 화면 중앙을 지나간다.
  • 클레이를 맞추면 다음 라운드가 시작된다. 단, 이전 라운드에서 맞춘 클레이가 지나가는 경로에서는 라운드가 초기화되어도 더 이상 클레이가 지나가지 않는다.
  • j번 라운드에 명중시킨 클레이가 지나가던 경로가 화면 아래에서 부터 i번째 경로라면 이번에 얻는 점수는 ( b[i] ×)이다.
  • 더 이상 맞출수 있는 클레이가 없으면 게임이 종료된다.

정진이는 게임을 플레이해서 얻을 수 있는 최고 점수가 궁금하다. 정진이를 도와주자.

입력

첫째 줄에는 클레이가 지나가는 경로의 개수 N이 주어진다.

다음 N개의 줄에는 두 정수 쌍 (a[i]b[i])가 주어진다. 화면 아래에서 가까운 순서가 i번째인 경로에서 클레이가 화면 중앙을 지나가는 간격이 a[i]이고 그 클레이를 맞추었을 때의 점수가 b[i]이다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

제한

1 ≤ N ≤ 16

1 ≤ a[i] ≤ 100

1 ≤ b[i] ≤ 100

예제 입력 1

4
2 4
4 2
6 8
8 6

예제 출력 1

58

예제 입력 2

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

예제 출력 2

1496

예제 입력 3

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

예제 출력 3

12920

예제 입력 4

5
17 1
23 2
17 2
23 3
17 1

예제 출력 4

31

출처

University > 인하대학교 > 2021 IGRUS Newbie Programming Contest J번