Fibonacci Presents

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

Sample Output


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.


  • 0
    aeternalis1  commented on Aug. 1, 2017, 9:15 p.m. edit 3

    What a meme

  • 0
    aeternalis1  commented on July 25, 2017, 11:02 p.m. edited

    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?

    • 0
      mouad978  commented on Feb. 17, 2017, 10:08 a.m.

      lol 1

  • 0
    onlyIfStatement  commented on Jan. 1, 2017, 6:13 p.m.

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

    • 1
      r3mark  commented on Jan. 1, 2017, 6: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, 6:23 p.m.

        Im not saying its wrong im just hoping for a pointer

        • 0
          r3mark  commented on Jan. 1, 2017, 6:26 p.m.

          We'll tell you after the contest is over!

          • 0
            pulkitsja  commented on Jan. 2, 2017, 1:58 a.m.

            Is the contest over, can we discuss?

            • 0
              r3mark  commented on Jan. 2, 2017, 2: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, 4:08 a.m.

                OK, Thank you.

  • 0
    Ken_Shi  commented on Jan. 1, 2017, 6:10 p.m. edited


  • 0
    rameshaggarwal  commented on Jan. 1, 2017, 1: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, 1:42 p.m. edited

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

  • 0
    imaxblue  commented on Jan. 1, 2017, 10:25 a.m. edited

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