E. Vacation Planning
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Trotles is on a well deserved vacation. He has 3 whole days where he wants to do activities that will make him as happy as possible. However, because he loves sleep, he must sleep for 8 hours every day, giving him 16 hours per day to do activities.

There is a list of $$$N$$$ activities, the $$$i$$$th taking a certain amount of hours $$$t_i$$$ to do and giving Trotles happiness $$$h_i$$$. Trotles can only do one activity at a time. He also can't do the same activity across multiple days, meaning every activity must be completed the day he starts it.

Find the maximum amount of happiness Trotles is able to achieve if he optimally plans his vacation.

Input

The first line consists of a single integer $$$N$$$ $$$(1 \leq N \leq 1000)$$$, the number of activities.

The next $$$N$$$ lines consists of two integers $$$t$$$ and $$$h$$$, describing an activity that takes $$$t$$$ hours and gives $$$h$$$ happiness. $$$(1 \leq t \leq 16, 1 \leq h \leq 1000)$$$

Output

Output a single integer that is the maximum amount of happiness Trotles can achieve.

Example
Input
6
8 2
8 1
9 1
12 2
16 5
4 10
Output
20