시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB8581178216.942%

문제

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

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

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

입력

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

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

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

출력

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

예제 입력 1

3
5 555
8 195
13 651
15

예제 출력 1

750

예제 입력 2

3
5 555
8 195
13 751
15

예제 출력 2

751

예제 입력 3

6
55 1562
5 814
55 1962
8 996
2 716
34 1792
94

예제 출력 3

4568

예제 입력 4

1
13 89
1

예제 출력 4

0

예제 입력 5

3
27777890035288 9419696870097445
53316291173 6312623457097563
165580141 8848283653257131
27777900000000

예제 출력 5

15160907110354694

출처