Cracking Eggs with Eggs

Interview

Time limit2sMemory limit512 MB

Summary

Each egg in a row is lifted from the left and hits one other unbroken egg once, and the task is to find the maximum number of eggs that can break.

Level: Medium4 of 10
Topics: Backtracking, Recursion
Solved: No attempts yet

Problem

A programmer's basic skill is said to be being unable to do a single push-up, but Inbeom is one of the few programmers whose big three total exceeds 500. Each time Inbeom submits a wrong answer on the online judge, he does five pull-ups, training his brain and muscles at the same time. Knowing that diet matters for building muscle, he skips a breakfast of rice or bread and makes steamed egg with plenty of protein instead.

To cook it, he has to crack eggs. His strength is so great that when he cracks them on the marble countertop, the shells shatter and cleanup becomes hard. Yuhyeon suggested a good solution: crack eggs by hitting them with other eggs. Inbeom found that eggs hitting each other split their shells neatly, so he decided to prepare his meals this way. Yuhyeon also gave him a puzzle that trains his brain while he cooks.

Each egg has a durability and a weight. When two eggs collide, each egg's durability decreases by the weight of the other egg. An egg breaks when its durability becomes 0 or less. For example, let egg 1 have durability 7 and weight 5, and egg 2 have durability 3 and weight 4. If egg 1 hits egg 2, egg 1 loses 4 durability and becomes 3, and egg 2 loses 5 and becomes -2. Egg 1 does not break, but egg 2 does.

The puzzle Yuhyeon gave is about eggs in a row. Starting from the left, pick up each egg in turn, and let it hit another egg exactly once, so that as many eggs as possible break. The process is as follows: (1) Pick up the leftmost egg. (2) With the egg in your hand, hit one of the other unbroken eggs. If the egg in your hand is broken, or no other unbroken egg exists, skip the hit. Then put the egg in your hand back in its original place and go to step (3). (3) Pick up the egg one position to the right of the egg you picked up most recently, and repeat step (2). If the most recently picked up egg is already the rightmost egg, the process ends.

Using this process, find the maximum number of eggs Inbeom can break, given the durability and weight of each egg in order.

Input

The first line contains the number of eggs $N$ ( $1 \le N \le 8$ ). The next $N$ lines describe the eggs. Line $i+1$ contains the durability $S_i$ ( $1 \le S_i \le 300$ ) and the weight $W_i$ ( $1 \le W_i \le 300$ ) of the egg in position $i$ from the left, separated by a single space.

Output

Print the maximum number of eggs Inbeom can break on the first line.

Examples5

Example 1
Input
```
3
8 5
1 100
3 5
```
Expected output
```
3
```
Example 2
Input
```
3
1 100
8 5
3 5
```
Expected output
```
2
```
Example 3
Input
```
1
123 45
```
Expected output
```
0
```

Example 4

Input

Expected output

Example 5

Input

Expected output