Description

Although this is a game, it is not a joke. (これは、ゲームであっても遊びではない)

── Kayaba Akihiko

Sword Art Online is a fully immersive VR game operates with NerveGear, which completely controls the player's consciousness by redirecting the signals the brain sends to the body and sending its own waves to stimulate the five senses.

Kirito, known as the Black Swordsman, is the fastest player in SAO. He is so fast that he even get the hidden skill named nitoryu (二刀流), which will be given to the fastest player.

He solos a lot, beats lots of monsters, gains huge amounts of experiences, and levels up. Now, he has some skill points to spend.

He wants to become faster and faster, so he would like to spend all skill points to level up those speed-based skills, and he needs to find out the best strategy in order to get the maximum speed he can reach.

Although he is a solo player, he still asks you for help. Please help him find out the best strategy so that he can equip his second sword and cast Star Burst Stream in 10 seconds.

Kirito casting "Star Burst Stream"

There are exactly $n$ skills. The maximum level of each skill is $x$. The initial level of Kirito's skills are $a_1,a_2,\dots,a_n$. And the number of skill points that he can spend is $m$. The formula of calculating speed $S$ is:

where $A,\ B$ is given. Note that $[a_i==x]=1$ if condition $(a_i==x)$ is true, $0$ otherwise.

Each skill points can increase the level of exactly one skill by $1$ (if it's not equal to $x$ yet). You are going to find out all $a_i'\ (a_i\le a_i'\le x)$, which is the level of $i$-th skill after leveling up, such that the speed $S$ has maximum value.

Take sample as example:

Skill levels are initially $(12,11,1,10,12,3,9,16,15,8)$, and we have $24$ skill points to spend.

The best strategy is to spend $(+0,+0,+9,+0,+0,+7,+2,+1,+2,+2)$ skill points ($23$ skill points are spent) to the corresponding skill, and the skill levels will become $(12,11,10,10,12,10,11,17,17,10)$.

The speed $S$ is:

Input

The first line contains $5$ integers: $n,\ x,\ A,\ B,\ m$, respectively.

The next line is the sequence $a_1,a_2,\dots,a_n$, each number is separated by a space.

$1\le n\le 10^5,\ 1\le x\le 10^9,\ 0\le A,B,\le 10^3,\ 0\le m\le 10^{15},\ 0\le a\le x$

Output

The first line should be the maximum value of $S$.

The next line print $n$ integers $a_1',a_2',\dots,a_n'$ separated by a space, where $a_i'$ is the level of $i$-th skill after spending skill points.

If there are multiple answers of $a_i'$, print any. All valid and correct answer will be accepted.

Sample Input  Download

Sample Output  Download

Tags

Discuss