Fibonacci Knapsack

Time limit2sMemory limit128 MB

Summary

Pick items whose weights are Fibonacci numbers into a bag of capacity C to maximize total value, where N is at most 50 and all numbers fit in 64 bits.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Math, Number theory
Solved: No attempts yet

Problem

There are N items and one bag. Each item has a weight and a value, and the bag can hold total weight at most C. Choose some of the items so that the total value in the bag is as large as possible.

This is a 0/1 knapsack problem, but the usual O(2^N) exhaustive search or O(N × sum of weights) dynamic programming is too large for the limits. Instead, every item weight is guaranteed to be a Fibonacci number.

In this problem, the first and second Fibonacci numbers are 1 and 2. Each following number is the sum of the previous two numbers, so the sequence begins 1, 2, 3, 5, 8, 13, ... .

Input

The first line contains N. N is a positive integer no greater than 50.

Each of the next N lines contains the weight and value of one item. Both numbers are positive integers no greater than 10^16, and every weight is a Fibonacci number as defined above.

The last line contains C, the maximum total weight the bag can hold. C is a positive integer no greater than 10^16.

Output

Print the maximum possible total value of the items that can be placed in the bag.

Examples5

Example 1
Input
```
3
5 555
8 195
13 651
15
```
Expected output
```
750
```
Example 2
Input
```
3
5 555
8 195
13 751
15
```
Expected output
```
751
```

Example 3

Input

Expected output

Example 4
Input
```
1
13 89
1
```
Expected output
```
0
```

Example 5

Input

3
27777890035288 9419696870097445
53316291173 6312623457097563
165580141 8848283653257131
27777900000000

Expected output

15160907110354694