앞으로 N일 동안만 일할 수 있는 작업자가 있다. N+1일째부터는 자리를 비우므로, 모든 작업은 늦어도 N일째에 끝나야 한다.

날마다 작업 의뢰가 하나씩 잡혀 있다. i일에 시작하는 작업은 완료까지 Ti일이 걸리고(i일부터 i+Tiㅡ1일까지 차지), 완료하면 보수 Pi를 받는다. 한 번 작업을 시작하면 끝날 때까지 다른 작업을 시작할 수 없으며, 수락하지 않고 건너뛰는 날이 있어도 된다.

N = 7인 경우의 다음 의뢰표를 보자.

1일의 작업은 3일이 걸리고 보수는 10이다. 1일 작업을 수락하면 2일·3일의 작업은 시작할 수 없다. 2일의 작업을 수락하면 3~6일의 작업을 시작할 수 없다. 또한 6일의 작업(4일 소요)과 7일의 작업(2일 소요)은 N일 안에 끝나지 않으므로 수락할 수 없다.

이 예에서 최대 수익은 1일, 4일, 5일의 작업을 골랐을 때의 10+20+15=45이다.

작업을 적절히 골랐을 때 얻을 수 있는 수익의 최댓값을 구하는 프로그램을 작성하라.

입력

첫째 줄에 N(1 ≤ N ≤ 15)이 주어진다.

이어지는 N개의 줄에 1일부터 N일까지의 Ti와 Pi가 순서대로 한 줄에 한 쌍씩 공백으로 구분되어 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 얻을 수 있는 최대 수익을 출력한다.

예제 입력 1

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 출력 1

45

예제 입력 2

10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

예제 출력 2

55

예제 입력 3

10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6

예제 출력 3

20

예제 입력 4

10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

예제 출력 4

90