Santa was very busy traveling around the world handing out presents. So busy, in fact, that he forgot to give you one! Not offended in the least, (it's *just* a Christmas present) you decide to break into Santa's place and claim what is rightfully yours.

Arriving at Santa's house, you realize that his bag can store items with a total mass equal to the Fibonacci number. **Any amount more or less would result in very un-Christmas-y consequences.** Looking around, you notice a heap of presents. The present has a mass equal to the (1-based) Fibonacci number, and a coolness factor of . Deciding that Santa needs a quick reminder to bring you a present next year, you decide to **maximize** the coolness of the presents you "liberate".

#### Input Specification

Line : Two space separated integers and , the mass capability of Santa's sack and the number of presents, respectively.

Lines : an integer , the present's coolness.

#### Output Specification

A single integer, the maximal coolness of stolen items. If this is not possible, output `-1`

instead.

#### Sample Input

```
12 11
0
0
1
4
7
2
8
10
8
12
10
```

#### Sample Output

`37`

#### Explanation for Sample Output

The presents have masses of , , , , , , , , , and , while the required mass is . Take the presents with mass of , , , and , for a total coolness of .

## Comments

What a meme

What's wrong with my code?I've reviewed and revised it quite a few times but I can't AC anything except the edge cases. It runs the sample correctly along with other test cases I made up. Is it a problem with my method or is it something else?

Any tips?

lol 1

Any tips for why case #13 would cause an issue?

All I can say is that all the test cases have been verified and they are correct, including test case 13.

Im not saying its wrong im just hoping for a pointer

We'll tell you after the contest is over!

Is the contest over, can we discuss?

Yes, you may. Editorials will be released tomorrow.

Btw, test case 13 was an edge case when k=1 and n>=2.

OK, Thank you.

nvm233

Is the sample input correct? why can't we just take all except 89 weight for coolness of 52?

Re-read the question, your combination does not achieve the required mass

K can actually be up to 10^9. Sorry for any inconvenience caused by this problem. The statement has been updated.