1128번 - 피보나치 냅색

종혁이는 물건 N개를 가지고 있고, 각 물건의 무게와 가격을 알고 있다. 또, 가방을 하나 가지고 있다. 가방에 담을 수 있는 무게의 최댓값은 C이다. 종혁이는 가방에 물건을 넣으려고 한다. 이때, 가방에 들어있는 물건의 가격의 합을 최대로 만들려고 한다.

이 문제는 유명한 냅색문제이다. 따라서, 시간 복잡도가 O(2^N) 또는 O(N×무게의 합)이기 때문에 풀 수 없다. 따라서, 특별한 조건이 있다. 물건의 무게는 모두 피보나치 수이다.

첫 번째와 두 번째 피보나치 수는 1과 2이고, 그 다음 수는 이전의 두 수를 더해서 만든다. 즉, 피보나치 숫자는 1, 2, 3, 5, 8, 13, ... 으로 시작하게 된다.

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다.

둘째 줄부터 N개의 줄에는 각 물건의 무게와 가격이 주어진다. 무게와 가격은 모두 10¹⁶보다 작거나 같은 자연수이다.

마지막 줄에는 C가 주어진다. C는 10¹⁶보다 작거나 같은 자연수이다.

첫째 줄에 가방에 들어있는 물건의 가격의 합의 최댓값을 출력한다.