Greeting

Interview

Time limit2sMemory limit128 MB

Summary

Given health costs and joy values for up to 20 people, pick a subset maximizing total joy while keeping total health loss below 100.

Level: Easy3 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

Sejun has spent a long time in the hospital after surgery. Now he wants to thank the people who cared about him while he was hospitalized.

There are N people, numbered from 1 to N. If Sejun greets person i, he loses L[i] health and gains J[i] joy. He can greet each person at most once.

Sejun starts with 100 health and 0 joy. If his health becomes 0 or negative, he cannot feel any joy. Choose whom he greets so that his health remains positive, and find the maximum joy he can gain.

Input

The first line contains the number of people, N. (N <= 20)

The second line contains the health losses L[i] for people 1 through N, in order.

The third line contains the joy values J[i] for people 1 through N, in order.

Every health loss and joy value is an integer between 0 and 100, inclusive.

Output

Print the maximum joy Sejun can gain.

Examples6

Example 1
Input
```
3
1 21 79
20 30 25
```
Expected output
```
50
```
Example 2
Input
```
1
100
20
```
Expected output
```
0
```

Example 3

Input

8
100 15 1 2 3 4 6 5
49 40 1 2 3 4 5 4

Expected output

Example 4
Input
```
4
100 50 20 13
20 30 40 50
```
Expected output
```
120
```

Example 5

Input

8
100 26 13 17 24 33 100 99
34 56 21 1 24 34 100 99

Expected output

Example 6

Input

12
1 1 1 1 1 1 1 1 1 1 1 1
100 100 100 100 100 100 100 100 100 100 100 100

Expected output