Informatica Online Judge

  한계 돌파 [1945 / 0799]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (34th 양준원)]
Writer ID : [gs16059]

Background

국내 인기 게임 제니스스토리는 특별한 날을 맞아 이벤트를 시작했다. 이번 이벤트는 자신이 키운 캐릭터의 레벨이 높을 수록 더 좋은 보상을 준다고 한다.

이 소식을 들은 제니스스토리 중독 유저 캐티는 최대한 많은 이익을 얻기 위해 캐릭터들을 키우려고 한다.

제니스스토리는 1레벨부터 시작하여 다음 레벨로 넘어가기 위해서는 a_i에 해당하는 시간을 소모해야 넘어갈 수 있다. 또한 이벤트 기획자 WK는 많은 유저한테 이벤트의 혜택을 건내주기 위해서 한번에 3레벨을 언제든지 올릴 수 있는 기회를 주었다고 한다.

캐티는 반복적인 것을 싫어하고 심각한 결벽증 환자라 캐릭터를 키울 때 같은 방법을 통해 레벨을 올리지 않고, 모든 캐릭터는 레벨이 같아야만 한다. 또한 캐티는 i레벨까지 키울 수 있는 모든 경우를 반드시 키운다고 한다.

시험기간인 캐티는 주어진 시간안에 최대한 많은 캐릭터를 키우려고 하지만 캐티는 제니스스토리 중독 유저라 레벨을 정해주지 않으면 주어진 시간을 초과하고 결국 시험을 망칠 것이다.

불쌍한 캐티가 시험을 망치지 않도록 캐티가 키울 캐릭터의 레벨을 정해주도록 하자.

단, 문제 내 연산 값은 2^63-1을 넘지 않는다.

Input

입력 첫째 줄에는 최대 레벨 n과 주어진 시간 m이 주어진다. (1<=n<=65000, 1<=m<=2^63-1)

입력 둘째줄에는 레벨에 따른 소요시간 a_i가 n번에 걸쳐 주어진다. (0<=a_i<=30)

Output

주어진 시간안에 키울 수 있는 캐릭터의 최대 레벨을 출력한다.

IO Example

입력
4 10
2 4 6 8

출력
3

(4레벨까지 키우는 데 걸리는 시간은 (2+4+6)+(2)이므로 주어진 시간을 초과하고 3레벨까지 키우는 시간은 (2+4)이다.)

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