E-SHOPPING CARDS

Due to the significant increase in prices, many countries issue prepaid electronic cards for their citizens, which they can use for various purchases (e.g., food, fuel, etc.). The total amount that can be spent is determined based on economic data. The allocation is made to families based on income criteria, in the following way:

Families are divided into ~\mathbf{N}~ economic groups based on their total annual income. Families in the first group have lower income than those in the second group, and so on. Each family in the same economic group will be given a prepaid electronic card of the same value. The Ministry of Finance has decided that if the value of the cards in the first group is equal to ~\mathbf{X_1}~ euros, then the value of the cards in the second group should be equal to ~\mathbf{X_2 = A \cdot X_1}~ euros (where 0 < ~\mathbf{A}~ < 1 is a given number), and the value of the cards in the third group should be equal to ~\mathbf{X_3 = A \cdot X_2}~ euros, and so on. All card values in euros should be integers — any cents resulting from the above operations will be truncated. Additionally, if the value of the cards for an economic group is less than 10 euros, then no aid will be provided to that economic group.

For example, let ~\mathbf{A}~ = 0.5 and the cards in the first group have a value of ~\mathbf{X_1}~ = 100 euros. Then, the cards for all economic groups should have the following values:

• Group 1   ~\mathbf{X_1}~ = 100 euros
• Group 2   ~\mathbf{X_2}~ = 50 euros
• Group 3   ~\mathbf{X_3}~ = 25 euros
• Group 4   ~\mathbf{X_4}~ = 12 euros   (50 cents truncated)
• Group 5   ~\mathbf{X_5}~ = 0       (it would be 6 < 10 euros)
• Group 6   ~\mathbf{X_6}~ = 0       (it would be 3 < 10 euros)

The Ministry of Finance has defined the maximum total amount ~\mathbf{B}~ that can be allocated as aid in this way. They also know that ~\mathbf{C_1}~ families belong to the first economic group, ~\mathbf{C_2}~ families belong to the second economic group, and so on. They ask for your help to determine the values of the cards in such a way that the first economic group receives cards of the highest possible value, without exceeding the maximum total amount.

Problem

Develop a program in one of the IOI languages (PASCAL, C, C++, Java) that reads the number of economic groups, the number of families per economic group, the constant ~A~, and the maximum total amount that can be allocated. our program should print the total amount to be allocated and the values of the cards for each economic group.

Input files:

The input files with the name coupon.in are text files with the following structure: The first line contains three numbers separated in pairs by a space: the number of economic groups ~\mathbf{N}~, the constant ~\mathbf{A}~, and the maximum total amount ~\mathbf{B}~. The numbers ~\mathbf{N}~ and ~\mathbf{B}~ are integers, while the constant ~\mathbf{A}~ is given with at most three decimal digits. In each of the next ~\mathbf{N}~ lines, there is an integer ~\mathbf{C_i}~ (where ~1 \le i \le N~): the number of families belonging to the i-th economic group.

Output Files:

The line must contain exactly one integer: the total amount to be allocated to all families. Each of the next ~\mathbf{N}~ lines must contain an integer ~\mathbf{X_i}~ (where ~1 \le i \le N~): the value of the e-card that will be allocated to each family of the i-th economic group or 0 if no aid will be allocated to the i-th economic group.

Constraints:

• ~1 \le N \le 1.000~
• ~0 < A < 1~
• ~1 \le B \le 1.000.000.000~
• ~1 \le C_i \le 1.000.000~

Examples of input-output files:

Example 1

STDIN (coupon.in)

6 0.5 1000000
10000
3000
1000
400
100
10

STDOUT (coupon.out)

991000
84
42
21
10
0
0

Example 2

STDIN (coupon.in)

10 0.8 100000000
10000
25000
120000
40000
15000
6000
1520
800
420
170

STDOUT (coupon.out)

99921970
736
588
470
376
300
240
192
153
122
97

Explanation of examples:

"In the first example, each family in the 1st economic group is allocated an electronic card worth 84 euros. There are 10,000 families in this group, receiving a total of 10,000 · 84 = 840,000 euros. In the 2nd economic group, a total of 3,000 · 42 = 126,000 euros will be allocated, in the 3rd economic group, a total of 1,000 · 21 = 21,000 euros will be allocated, while in the 4th economic group, a total of 400 · 10 = 4,000 euros will be allocated. No aid will be allocated to the 5th and 6th economic groups. The total amount to be allocated to all families is:"

In the second example, starting with 736 euros for the 1st economic group, the total amount is sufficient to provide aid to all economic groups.

Notes:

Formatting: In both the input and the output, each line terminates with a newline character.
Maximum execution time: 1sec.
Maximum available memory: 64MB.
Headers in the source code: At the beginning of your source code, you should use the following headers.

(* USER: username
LANG: PASCAL
TASK: coupon *)

for PASCAL coders

/* USER: username
LANG: C
TASK: coupon */

for C coders

/* USER: username
LANG: C++
TASK: coupon */

for C++ coders

/* USER: username
LANG: Java
TASK: coupon */

for Java coders

# USER: username
# LANG: Python
# TASK: coupon

for Python coders