Lesson 5

Programming problem. The standard knapsack dynamic program runs in time \(O(nB)\). This is much better than trying all \(2^{n}\) portfolios when the budget \(B\) is moderate. But if \(B\) is huge, a table of length \(B\) is hopeless, and we need a different exact tradeoff.

This is where the split \(F(x)=F_{\text{left}}(x)\cdot F_{\text{right}}(x)\) pays off. Expand each half into its roughly \(2^{n/2}\) portfolios, sort one half by price while remembering the best score available up to each price, and then for every portfolio of the other half look up the best affordable partner.

• Input format.  The first line contains two integers \(1 \le n \le 40\) and \(1 \le B \le 10^{15}\). The second line contains integers \(1 \le p_{1},\dotsc,p_{n} \le 10^{15}\). The third line contains integers \(1 \le r_{1},\dotsc,r_{n} \le 10^{9}\).


• Output format.  Output one integer: the maximum possible score of a portfolio whose total price is at most \(B\).

4 10
2 3 5 7
1 4 5 6

10

3 10
6 6 10
9 9 10

10

3 1000000000000
1000000000000 999999999999 7
8 9 3

9