시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 377 33 25 15.244%

문제

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

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

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

입력

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

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

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

출력

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

예제 입력

3
5 555
8 195
13 651
15

예제 출력

750

힌트

출처