You are in an electronics store. The structure of this store is best described as $N+1$ blocks (numbered $0$ through $N$) forming a straight line. Block $i$ is adjacent to block $i+1$ for all $0 ≤ i < N$. For every $i \ge 1$, block $i$ contains $Q_i$ copies of product $i$, each of which is worth $P_i$ HackerCoins. Block $0$ does not contain any products.

The store is holding a special event, offering its 3,141,592nd visitor a very special chance to take home whatever he or she can grab in a given amount of time, for free. And the winner has just been announced. Yes — it is you!

The rules are simple. You start in block $0$, which also contains a stationary cart. You have $t$ seconds to move around the store, picking some products and getting them to the cart. After that time you win whatever is in the cart. However, at any moment of time, it is forbidden to hold more than one copy of the same product. Also, you can drop the taken products only in the cart.

Thanks to your incredible strength, it takes you only exactly $1$ second to move to an adjacent block, regardless of how many products you are carrying. Picking up a copy of product $i$ takes you $W_i$ seconds, while placing anything in the cart takes no time.

The store has yet to decide how much time to give to you. For all integers $t$ such that $1 ≤ t ≤ T$, determine the maximum possible total worth of the products you can win, in HackerCoins.
 

Input

The first line contains two space-separated integers $N$ and $T$ — the number of blocks (not counting block $0$) and the limitation for the allowed time, respectively.

The second line contains $N$ space-separated integers: $Q_1$, $Q_2$, $\ldots$, $Q_N$ — the number of copies available of each product.

The third line contains $N$ space-separated integers: $P_1$, $P_2$, $\ldots$, $P_N$ — the worth (value) of each product, in HackerCoins.

The fourth line contains $N$ space-separated integers: $W_1$, $W_2$, $\ldots$, $W_N$ — the time needed to pick up a copy of each product, in seconds.

Output

Print one line containing $T$ space-separated integers, the $t$-th of which is the maximum total worth of the products you could obtain were you given $t$ seconds, in HackerCoins. Remember that you win only the products placed in the cart.

Constraints

$1 ≤ N ≤ 300$

$1 ≤ T ≤ 5\,000$

$1 ≤ Q_i ≤ 1\,000$

$1 ≤ P_i ≤ 100\,000$

$1 ≤ W_i ≤ 1\,000$

Note that the expected output feature for custom input is disabled for this contest.