Informatica Online Judge

 Prob No. 06E6 : 보스전 [CH02.2.Algorithm(Design)]

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


The Champion of this Problem (C++) : gst17083 - 0ms / 618byte
My Best Submission (C++) : N/A

[koistudy.net (unkonwn)]


Background

경곽이는 RPG게임에서 마지막 보스와의 전투를 시작했다. 마지막 보스는 바로 가장 친한 동료였다.

이 게임은 다른 게임과는 달리 HP가 음수가 되어야 전투불능인 상태가 된다.

따라서 HP가 0인 상태는 빈사상태로 아직 전투불능은 아니다.

마지막 전투가 어려운 이유는 보스가 전투불능이 되면 게임오버가 된다.

따라서 이 전투의 목적은 보스를 전투불능이 되지 않도록 하면서 HP를 최소로 만드는 것이다.

경곽이는 $n$개의 스킬을 사용할 수 있으며 각 스킬은 공격력 순으로 오름차순으로 정렬되어 있다.

경곽이의 각 스킬은 한 번씩만 사용할 수 있으며, 각 스킬이 보스에게 줄 수 있는 데미지는 다음과 같은 관계를 가진다.

$i>2$일 때, "$i$번째 스킬이 보스에게 주는 데미지" 는 "$i-1$번째 스킬이 보스에게 주는 데미지" + "$i-2$번째 스킬이 보스에게 주는 데미지" 보다 크거나 같다.

이를 식으로 표현하면..

$d_i$는 $i$번째 스킬이 보스에게 주는 데미지라고 하면

$d_i≥d_{i-1} + d_{i-2}$

이다.

이러한 조건을 만족하는 스킬을 $n$개 가진 경곽이는 보스를 전투불능으로 만들지 않으면서 줄 수 있는 최대 데미지를 구해야 한다.

Input

첫 번째 줄에 스킬의 수 $n$과 보스의 체력 $h$가 공백으로 구분되어 주어진다.

두 번째 줄부터 $n$줄에 걸쳐서 각 스킬이 보스에게 주는 데미지가 주어진다.

[입력값의 정의역]
$n≤1,000$ 인 자연수
$1≤h≤2^{30}$ 인 자연수

Output

보스를 전투불능으로 만들지 않는 최대 데미지를 출력한다.

IO Example

입력
3 15
1
10
20

출력
11

* 설명 : 1과 10인 스킬을 활용하면 11의 데미지를 줄 수 있다. 이보다 더 많은 데미지를 주려고 하면 보스는 전투불능이 되어 게임오버가 된다.

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