Informatica Online Judge

  밸런스 [0214 / 00D6]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 94   Total Tried : 1486


The Champion of this Problem (C++) : gs16103 - ms / 387byte
My Best Submission (C++) : N/A

[]

Background

명 윅은 양팔저울을 가지고 있다.

그리고 그는 N (1<= N <= 1000)개의 무게 추 세트를 가지고 있다.

당신은 이 무게추들을 이용하여 최대한 정확히 명 윅의 무게를 측정하고자 한다.

그는 양팔저울의 한쪽에 올라가고 그의 무게 C(1<=C<2^30)를 최대한 정확하게 측정하기 위해서 다른 한 쪽에 무게 추를 올려놓고자 한다.

그러나 그 무게 추들의 무게의 합이 C를 초과할 수는 없다.

C를 초과하면 명 윅은 저울을 부숴버린다. 그리고 명윅 측에는 무게 추를 올릴 수가 없다.

그의 무게를 최대한 정확하게 측정하기 위한 추의 조합 무게의 합을 구하는 것이 문제의 목적이다. 단 이 무게추 세트는 다음과 같은 성질이 있다고 한다.

무게추의 순서는 오름 차순으로 주어지며, k번째 무게추는 (단 k>=3) 반드시 k-1번째 무게 추 + k-2번째 무게 추의 합보다 같거나 크다고 한다.

Input

공백으로 구분된 두 정수 N과 C가 입력으로 주어진다.

(모든 추의 무게는 10^9을 초과하지 않는다.)

Output

명 윅의 무게를 가장 비슷하게 측정할 수 있는 정수값을 출력한다. 단 그값은 C를 넘어서는 안된다.

IO Example

입력
3 15
1
10
20

출력
11



출처 : USACO (http://ace.delos.com)

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]