Canal Convoy Lane Toggle Cost

A cargo canal is divided into n consecutive segments, numbered 1 to n. Each segment can be traveled through one of two parallel lanes: the Standard lane or the Toll lane. Traveling segment i in the Standard lane costs standard_i; traveling it in the Toll lane costs toll_i. A convoy starts just before segment 1, in the Standard lane. At the start of any segment the convoy may move from the Standard lane into the Toll lane by paying a one-time gate fee fee (this fee may be paid again to re-enter the Toll lane later, if the convoy has since dropped back to Standard); moving back from the Toll lane into the Standard lane never costs anything. For every j from 1 to n, report the minimum total amount the convoy must have spent to finish traveling segments 1 through j, ending that prefix in whichever lane is cheaper.

Input format

Line 1: two integers n and fee. Line 2: n integers standard_1 ... standard_n. Line 3: n integers toll_1 ... toll_n.

Output format

n integers separated by single spaces, on one line: for each j from 1 to n, the minimum total cost to finish segments 1 through j.

Constraints

• 1 <= n <= 1000
• 0 <= fee <= 10^6
• 0 <= standard_i, toll_i <= 10^6 for every i

3 2
1 2 1
3 1 1

1 3 4

5 4
1 1 1 1 1
2 2 2 2 2

1 2 3 4 5