Lesson 3

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 value of \[\sum_{i=1}^{n} |p_{i} a_{i}-t_{i}|\] under the budget constraint \(\sum_{i} p_{i} a_{i}\le B\).

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


• 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