Lesson 6

Programming problem.

Implement a program for the following task. There are \(n\) stocks. For stock \(i\), the price is \(p_{i}\), the target amount is \(t_{i}\), and at most \(m_{i}\) shares may be bought. Find the minimum possible tracking error under budget \(B\).

The budget and prices may be huge, so a table of length \(B\) is not allowed. It is guaranteed that after processing any prefix of stocks, the nondominated frontier contains at most \(200000\) points.

• Input format.  The first line contains two integers \(1 \le n \le 60\) and \(0 \le B \le 10^{18}\). The second line contains integer prices \(1 \le p_{1},\dotsc,p_{n} \le 10^{18}\). The third line contains integer target amounts \(0 \le t_{1},\dotsc,t_{n} \le 10^{18}\). The fourth line contains integer upper bounds \(0 \le m_{1},\dotsc,m_{n} \le 30\).


• Output format.  Output one integer: the minimum possible tracking error.

4 18
4 6 9 11
5 5 8 10
2 2 2 1

15

2 6
6 6
5 5
1 1

6