Inventory Ordering Optimization

A company estimates that the market demand for a product in the i^th month is given by \(U_i\), and the unit ordering price in month \(i\) is \(d_i\). Any unsold product carried from the previous month incurs a storage cost of \(m\) per unit. The ordering happens at the beginning of each month and the products are immediately available; if they are sold in the same month, no storage cost is applied. The initial inventory at the beginning of month 1 and the ending inventory at the end of month \(n\) are both 0. Moreover, the warehouse has a capacity of \(S\) units which limits the amount of product held immediately after each order.

Your task is to determine an ordering plan over \(n\) months, i.e. how many units to order each month \(x_i\) (for \(1 \le i \le n\)) such that the inventory update \[ I_i = I_{i-1} + x_i - U_i, \quad I_0 = 0, \quad I_n = 0, \] with the constraint that at the moment of delivery \(I_{i-1} + x_i \le S\), and to minimize the total cost given by \[ \text{Total Cost} = \sum_{i=1}^{n} \Big( d_i \cdot x_i + m \cdot I_i \Big). \]

If there is no feasible plan satisfying the constraints, output an appropriate message.

inputFormat

The input consists of three lines:

• The first line contains three integers \(n\), \(m\), and \(S\) representing the number of months, the per‐unit storage cost, and the warehouse capacity, respectively.
• The second line contains \(n\) integers \(U_1, U_2, \ldots, U_n\), where \(U_i\) is the demand in month \(i\).
• The third line contains \(n\) integers \(d_1, d_2, \ldots, d_n\), where \(d_i\) is the ordering price in month \(i\).

It is guaranteed that \(n \ge 1\) and the test cases will have at least 3 different cases.

outputFormat

If a feasible ordering plan exists, output two lines:

• The first line contains the minimum total cost.
• The second line contains \(n\) integers \(x_1, x_2, \ldots, x_n\) separated by spaces, which represent the units ordered in each month in an optimal plan.

If no feasible ordering plan exists, output the message "No feasible solution".

sample

3 1 10
5 3 4
2 3 1

23
5 3 4