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 
~k^{th}~ Fibonacci number. Any amount more or less would result in very un-Christmas-y consequences. Looking around, you notice a heap of 
~n~ presents. The 
~i^{th}~ present has a mass equal to the ~i^{th}~ (1-based) Fibonacci number, and a coolness factor of 
~c_i~. 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 
~1~: Two space separated integers 
~k~ 
~(1 \le k \le 1\,000\,000\,000)~ and ~n~ 
~(1 \le n \le 1\,000\,000)~, the mass capability of Santa's sack and the number of presents, respectively.
Lines 
~2 \dots n+2~: an integer ~c_i~ 
~(0 \le c_i \le 1\,000\,000)~, the ~i^{th}~ 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 ~1~, ~1~, 
~2~, 
~3~, 
~5~, 
~8~, 
~13~, 
~21~, 
~34~, 
~55~ and 
~89~, while the required mass is 
~144~. Take the presents with mass of ~3~, ~5~, ~13~, ~34~ and ~89~, for a total coolness of 
~4+7+8+8+10=37~.
Comments
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.
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