Fibonacci Knapsack

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, ... .

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.

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