클레이 사격 게임

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

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

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

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

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

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

1 ≤ N ≤ 16

1 ≤ a[i] ≤ 100

1 ≤ b[i] ≤ 100