저울

면접 대비

시간 제한1초메모리 제한1024 MB

요약

앞의 두 무게의 합 이상인 N개의 무게가 주어질 때, 합이 C를 넘지 않는 가장 큰 질량을 구합니다.

난이도: 보통10점 중 5점
유형: 그리디, 백트래킹
정답자: 아직 제출이 없습니다

문제

Farmer John은 소의 무게를 재는 저울을 가지고 있다. 그에게는 질량을 알고 있는 추 $N$ 개 ( $1 \le N \le 1000$ ) 도 있으며, 각 추의 질량은 31비트 안에 들어간다. 소의 무게를 잴 때는 소를 저울 한쪽에 올리고, 반대쪽에 추를 더해 양쪽이 균형을 이룰 때까지 올린다. 소는 기회만 생기면 추를 발로 차므로, 추는 소와 같은 쪽에 올릴 수 없다.

저울에는 최대 질량 등급이 있다. 한쪽에 올린 총 질량이 $C$ ( $1 \le C < 2^{30}$ ) 를 넘으면 저울이 부러진다.

추에는 특별한 성질이 있다. 질량이 작은 순서대로 나열했을 때, 세 번째 추부터는 각 추의 질량이 바로 앞의 두 추의 질량 합보다 크거나 같다.

이 추들로 정확히 잴 수 있는 최대 질량을 구하라. 사용하는 총 질량은 $C$ 이하여야 하므로, 모든 추를 저울에 올리지 못할 수도 있다. 추 목록과 저울의 최대 질량 $C$ 가 주어지면, 정확히 잴 수 있고 허용 범위 안에 있는 최대 질량을 출력한다.

입력

첫 줄에 공백으로 구분된 양의 정수 $N$ 과 $C$ 가 주어진다.

이어지는 $N$ 개의 줄에는 각각 추의 질량을 나타내는 양의 정수가 하나씩 주어진다. 질량은 오름차순으로 주어진다.

출력

첫 줄에 정확하고 안전하게 잴 수 있는 최대 질량을 정수 하나로 출력한다.

예제1

예제 1
입력
```
3 15
1
10
20
```
예상 출력
```
11
```