We have an array of n elements (1 <= n <= 60) We have to determine whats the maximum sum subsequence possible that is less than or equal to a value k (1 <= k <= 10^18). At most 15 of the elements in array, either a[i] >= 2*a[j] or a[j] >= 2*a[i] where j is not equal to i (1 <= a[i] <= 10^17)

This problem was asked in Visa OA and later also in Expedia OA and both the times I couldn't manage to get all test cases passes. The constraints are very big for any regular knapsack approach to work. I thought of dividing the array such that first one will have all those at most 15 elements which shows that mentioned property and rest are the regular ones, since 15 is very less we can use something like bitmasking, so choosing k1 from that set and rest k-k1 from other set. But I couldn't make this idea work it will end up a bruteforce maybe I'm missing some observation. Please help