Aman and Coding

Hard

Aman is learning to code again after a break of 6 months. Now aman is provided with n questions in a test and he is lazy so he wrote codes for every question but didn't complete most of the codes. We are provided with number of lines of code he wrote for every question. If he writes "m" lines of code for any question, that question is solved and he need not write any more lines of code for that.

Now aman can write "c" more lines of code before he will go to sleep. Score of test is sum of following value.

1. The number of questions that he completed is multiplied by a completion factor.
2. Minimum of lines of code of all the partially complete question is multiplied by a number (partial factor).

Now as aman will write only "c" more lines of code, help him decide in which questions he should write these lines of code.

You should output the maximum score of test possible and n integers representing the final number of lines of code for every question.

Constraints

1<=n<=100000
1<=m<=100000000
0<=cf<=1000
0<=pf<=1000
0<=m<=1000000000000000

Format

Input

The first line contains five space separated integers

1. n (number of questions)
2. m (lines of code after which question is complete)
3. cf (completion factor)
4. pf (partial factor)
5. c (number of lines of code aman can write)
   respectively.

The second line will contain n space separated integers representing the number of lines of code he already wrote for every question.

Output

In first line output the maximum test score aman can get.
In second line print n integers representing the final number of lines of code for every
question.

Example

Sample Input

4 6 12 1 7
1 3 1 1

Sample Output

14
2 6 2 2