## New Year's '17 P3 - Fibonacci Presents

View as PDF

Points: 10
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

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 .

• commented on Feb. 17, 2017, 3:08 p.m.

lol 1

• commented on Jan. 1, 2017, 11:13 p.m.

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

• commented on Jan. 1, 2017, 11:15 p.m.

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

• commented on Jan. 1, 2017, 11:23 p.m.

Im not saying its wrong im just hoping for a pointer

• commented on Jan. 1, 2017, 11:26 p.m.

We'll tell you after the contest is over!

• commented on Jan. 2, 2017, 6:58 a.m.

Is the contest over, can we discuss?

• commented on Jan. 2, 2017, 7:14 a.m.

Yes, you may. Editorials will be released tomorrow.

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

• commented on Jan. 2, 2017, 9:08 a.m.

OK, Thank you.

• commented on Jan. 1, 2017, 6:40 p.m.

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

• commented on Jan. 1, 2017, 6:42 p.m. edited