New Year's '17 P3 - Fibonacci Presents - DMOJ: Modern Online Judge

New Year's '17 P3 - Fibonacci Presents

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 $k^{th}$ $k^{t h}$ Fibonacci number. Any amount more or less would result in very un-Christmas-y consequences. Looking around, you notice a heap of $n$ $n$ presents. The $i^{th}$ $i^{t h}$ present has a mass equal to the $i^{th}$ $i^{t h}$ (1-based) Fibonacci number, and a coolness factor of $c_i$ $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$ $1$ : Two space separated integers $k$ $k$ $(1 \le k \le 1\,000\,000\,000)$ $(1 \leq k \leq 1 000 000 000)$ and $n$ $n$ $(1 \le n \le 1\,000\,000)$ $(1 \leq n \leq 1 000 000)$ , the mass capability of Santa's sack and the number of presents, respectively.
Lines $2 \dots n+2$ $2 \dots n + 2$ : an integer $c_i$ $c_{i}$ $(0 \le c_i \le 1\,000\,000)$ $(0 \leq c_{i} \leq 1 000 000)$ , the $i^{th}$ $i^{t h}$ present's coolness.

Output Specification

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

Sample Input

Copy

Sample Output

Copy

Explanation for Sample Output

The presents have masses of $1$ $1$ , $1$ $1$ , $2$ $2$ , $3$ $3$ , $5$ $5$ , $8$ $8$ , $13$ $13$ , $21$ $21$ , $34$ $34$ , $55$ $55$ and $89$ $89$ , while the required mass is $144$ $144$ . Take the presents with mass of $3$ $3$ , $5$ $5$ , $13$ $13$ , $34$ $34$ and $89$ $89$ , for a total coolness of $4+7+8+8+10=37$ $4 + 7 + 8 + 8 + 10 = 37$ .

Comments

0

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

lol 1

0

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

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

1

r3mark 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.

0

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

Im not saying its wrong im just hoping for a pointer

0

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

We'll tell you after the contest is over!

0

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

Is the contest over, can we discuss?

0

r3mark 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.

0

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

OK, Thank you.

0

rameshaggarwal 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?

0

imaxblue commented on Jan. 1, 2017, 6:42 p.m. ← edited →

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