P3423 [POI 2005] BAN-Bank Notes

`Byteotian Bit Bank(BBB)` has an advanced currency system. There are $n$ coin denominations with values $b_1, b_2, \cdots, b_n$. However, each coin has a limited quantity. Now we want to make a total value of $k$. Find the minimum number of coins needed. It is guaranteed that $k$ can be formed.

The first line contains an integer $n$. The second line contains $n$ integers $b_i$, the denominations of these $n$ types of coins. The third line contains $n$ integers $c_i$, the quantity of each of these $n$ types of coins. The fourth line contains an integer $k$.

The first line contains an integer, the minimum number of coins required. The second line contains $n$ integers, where the $i$-th number is how many coins of type $i$ are used. If there are multiple solutions, output any one of them.

For $100\%$ of the testdata, $1 \le n \le 200$, $1 \le b_1 < b_2 < \cdots < b_n \le 2 \times 10^4$, $1 \le c_i \le 2 \times 10^4$, $1 \le k \le 2 \times 10^4$. Translated by ChatGPT 5