Twisted Knapsack Problem(unbounded with Fibonacci constraint)

Question

I've encountered the following problem during two of my hiring challenges(on HackerEarth).The question is not available online, so here is the problem statement to the best of my memory:

Given a knapsack with M weight and n items, each with a positive weight w and positive value v(given as array weight[] and val[] ).Every item is available infinite times to be taken.But if you take a item x number of times, then all the other items(if taken) have to be taken x number of times.
Here x is a Fibonacci number less than 100.
Find the maximum value you can have while total weight of the knapsack is <= M.

constraints:
n <= 20
(M, weights, vals)<=1e9

Sample Test case:

n=2, M = 125
weight=[50, 25]
val =[100, 51]

for x=1: max val is 100+51 = 151

for x=2: max val is 2*100 = 200

for x=3: max val is 3*51 = 153

for x=5: max val is 5*51 = 255

for rest of the x: max val will be 0

Could anyone suggest how to approach it.
Here is what I did:

Generated all the possible subsets of items(using bitmasking) and for each subset, I kept on multiplying its weight with x = 1,2,3,5... until the weight exceeds M while keeping the count of max val obtained so far.After 2^n iterations, even though I had my answer, but it passed just the 3 out of 15 test cases and got TLEd for the rest.

Answer 1

I think one small optimization would pass all test cases. Precalculate the nearest smaller Fibonacci number for x. Now after generating all subset sum , divide m by the sum . Find the nearest smaller Fibonacci number of ( m / sum). Multiply it by sum. So the overall time complexity is O(2^n).