Description

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.

Input Format

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$.

Output Format

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.

3
2 3 5
2 2 1
10

3
1 1 1

Hint

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