Farmer John은 소 저울과 알려진 무게 $N$ ($1 \le N \le 1000$)개 추(31비트)를 한쪽에 씁니다. 소 한쪽, 추 다른 쪽에 평형까지 더합니다. 소와 같이 두면 기회마다 얼굴로 걷어찹니다. 한쪽 총 무게가 $C$ ($1 \le C < 2^{30}$) 초과면 저울이 깨집니다.

작은 순서로 세 번째부터 각 추는 앞 두 합 이상입니다.

정확히 잴 최대 무게를 구하며 총 $C$ 이하라 모든 추를 못 둘 수 있습니다.

목록과 용량으로 합법적 정확한 최대 무게를 구하세요.

입력

1번째 줄: 공백 구분 양의 정수 $N$, $C$.

$2..N+1$번째 줄: 양의 정수 추 무게 하나씩, 비감소 순서 보장.

출력

1번째 줄: 정확하고 안전한 최대 무게 정수.

예제

입력 1

3 15
1
10
20

출력 1

11

참고

추 세 개 1,10,20, 한쪽 최대 15입니다.

1과10으로11을 잽니다. 그보다 큰 만들 수 있는 무게는 모두 깹니다.