피보나치 냅색

물건 N개와 가방 하나가 있다. 각 물건에는 무게와 가격이 있고, 가방에는 총무게가 최대 C가 되도록 물건을 담을 수 있다. 가방에 담은 물건들의 가격 합이 최대가 되도록 물건을 고르려고 한다.

이는 0/1 냅색 문제이지만, 일반적인 O(2^N) 완전 탐색이나 O(N × 무게의 합) 동적 계획법으로는 제한 안에 풀 수 없다. 대신 모든 물건의 무게가 피보나치 수라는 조건이 주어진다.

이 문제에서 첫 번째와 두 번째 피보나치 수는 1과 2이다. 그 뒤의 수는 바로 앞 두 수의 합으로 정의되므로 수열은 1, 2, 3, 5, 8, 13, ... 으로 시작한다.

첫째 줄에 N이 주어진다. N은 50 이하의 자연수이다.

다음 N개의 줄에는 각 물건의 무게와 가격이 공백으로 구분되어 주어진다. 무게와 가격은 모두 10^16 이하의 자연수이며, 모든 무게는 위에서 정의한 피보나치 수이다.

마지막 줄에는 가방이 담을 수 있는 최대 무게 C가 주어진다. C는 10^16 이하의 자연수이다.

가방에 담을 수 있는 물건들의 가격 합의 최댓값을 출력한다.