Resignation

Junho works as a counselor and plans to resign.

He will leave the company on day $N+1$, counting today as day 1, so he wants to hold as many consultations as possible during the remaining $N$ days.

Junho asked his secretary to book as many consultations as possible, and the secretary booked one consultation per day, each with a different person.

Each consultation has a duration $T_i$, the number of days it takes to complete, and a payment $P_i$ received for completing it.

Consider the following schedule for $N = 7$.

The consultation booked on day 1 takes 3 days in total and pays 10. The consultation booked on day 5 takes 2 days in total and pays 15.

A consultation can take longer than one day, so Junho cannot hold every consultation. For example, if he holds the consultation on day 1, he cannot hold the consultations on days 2 and 3. If he holds the consultation on day 2, he cannot hold the consultations booked on days 3, 4, 5, and 6.

Also, Junho is no longer at the company on day $N+1$, so he cannot hold the consultations on days 6 and 7.

The maximum profit before resigning comes from holding the consultations on days 1, 4, and 5, for a profit of $10+20+15=45$.

Write a program that computes the maximum profit Junho can earn by choosing consultations optimally.

The first line contains $N$ ($1 \le N \le 15$).

Each of the next $N$ lines contains $T_i$ and $P_i$ separated by a space, given in order from day 1 to day $N$. ($1 \le T_i \le 5$, $1 \le P_i \le 1{,}000$)

Print the maximum profit Junho can earn on the first line.