Lesha plays the recently published new version of the legendary game hacknet. In this version character skill mechanism was introduced. Now, each player character has exactly n skills. Each skill is represented by a non-negative integer a_{i} — the current skill level. All skills have the same maximum level A.

Along with the skills, global ranking of all players was added. Players are ranked according to the so-called Force. The Force of a player is the sum of the following values:  The number of skills that a character has perfected (i.e., such that a_{i} = A), multiplied by coefficient c_{f}. The minimum skill level among all skills (min a_{i}), multiplied by coefficient c_{m}. 

Now Lesha has m hacknetian currency units, which he is willing to spend. Each currency unit can increase the current level of any skill by 1 (if it's not equal to A yet). Help him spend his money in order to achieve the maximum possible value of the Force.


-----Input-----

The first line of the input contains five space-separated integers n, A, c_{f}, c_{m} and m (1 ≤ n ≤ 100 000, 1 ≤ A ≤ 10^9, 0 ≤ c_{f}, c_{m} ≤ 1000, 0 ≤ m ≤ 10^15).

The second line contains exactly n integers a_{i} (0 ≤ a_{i} ≤ A), separated by spaces, — the current levels of skills.


-----Output-----

On the first line print the maximum value of the Force that the character can achieve using no more than m currency units.

On the second line print n integers a'_{i} (a_{i} ≤ a'_{i} ≤ A), skill levels which one must achieve in order to reach the specified value of the Force, while using no more than m currency units. Numbers should be separated by spaces.


-----Examples-----
Input
3 5 10 1 5
1 3 1

Output
12
2 5 2 

Input
3 5 10 1 339
1 3 1

Output
35
5 5 5 



-----Note-----

In the first test the optimal strategy is to increase the second skill to its maximum, and increase the two others by 1.

In the second test one should increase all skills to maximum.

Difficulty: competition

Starter code:

Solutions:
import itertools
import bisect

n, A, cf, cm, m = [int(x) for x in input().split()]
skills = [int(x) for x in input().split()]
sorted_skills = list(sorted((k, i) for i, k in enumerate(skills)))
bottom_lift = [0 for i in range(n)]
for i in range(1, n):
    bottom_lift[i] = bottom_lift[i-1] + i * (sorted_skills[i][0] - sorted_skills[i-1][0])
root_lift = [0 for i in range(n+1)]
for i in range(1, n+1):
    root_lift[i] = root_lift[i-1] + A - sorted_skills[n-i][0]

max_level = -1
for i in range(n+1):
    money_left = m - root_lift[i]
    if money_left < 0: break
    k = min(bisect.bisect(bottom_lift, money_left), n-i)
    money_left -= bottom_lift[k-1]
    min_level = min(A, sorted_skills[k-1][0] + money_left//k) if k > 0 else A
    level = cf*i + cm*min_level
    if max_level < level:
        max_level = level
        argmax = i
        argmax_min_level = min_level
        argmax_k = k

ans = [0 for i in range(n)]
for i, skill in enumerate(sorted_skills):
    if i < argmax_k:
        ans[skill[1]] = argmax_min_level
    elif i >= n - argmax:
        ans[skill[1]] = A
    else:
        ans[skill[1]] = skill[0]

print(max_level)
for a in ans:
    print(a, end = ' ')
    


def main():
    from bisect import bisect
    n, A, cf, cm, m = list(map(int, input().split()))
    skills = list(map(int, input().split()))
    xlat = sorted(list(range(n)), key=skills.__getitem__)
    sorted_skills = [skills[_] for _ in xlat]
    bottom_lift, a, c = [], 0, 0
    for i, b in enumerate(sorted_skills):
        c += i * (b - a)
        bottom_lift.append(c)
        a = b
    root_lift, a = [0], 0
    for b in reversed(sorted_skills):
        a += A - b
        root_lift.append(a)
    max_level = -1
    for A_width, a in enumerate(root_lift):
        if m < a:
            break
        money_left = m - a
        floor_width = bisect(bottom_lift, money_left)
        if floor_width > n - A_width:
            floor_width = n - A_width
        money_left -= bottom_lift[floor_width - 1]
        if floor_width > 0:
            floor = sorted_skills[floor_width - 1] + money_left // floor_width
            if floor > A:
                floor = A
        else:
            floor = A
        level = cf * A_width + cm * floor
        if max_level < level:
            max_level, save = level, (A_width, floor, floor_width)
    A_width, floor, floor_width = save
    for id in xlat[:floor_width]:
        skills[id] = floor
    for id in xlat[n - A_width:]:
        skills[id] = A
    print(max_level)
    print(' '.join(map(str, skills)))


def __starting_point():
    main()

__starting_point()

f = lambda: map(int, input().split())
g = lambda: m - l * p[l - 1] + s[l]

n, A, x, y, m = f()
t = sorted((q, i) for i, q in enumerate(f()))
p = [q for q, i in t]
s = [0] * (n + 1)
for j in range(n): s[j + 1] = p[j] + s[j]

l = r = n
F = L = R = B = -1
while 1:
    if p:
        while l > r or g() < 0: l -= 1
        b = min(p[l - 1] + g() // l, A)
    else: b, l = A, 0

    f = x * (n - r) + y * b
    if F < f: F, L, R, B = f, l, r, b

    if not p: break
    m += p.pop() - A
    r -= 1
    if m < 0: break

print(F)

p = [(i, B if j < L else q if j < R else A) for j, (q, i) in enumerate(t)]
for i, q in sorted(p): print(q)

f = lambda: list(map(int, input().split()))
g = lambda: m - l * p[l - 1] + s[l]

n, A, x, y, m = f()
t = sorted((q, i) for i, q in enumerate(f()))
p = [q for q, i in t]
s = [0] * (n + 1)
for j in range(n): s[j + 1] = p[j] + s[j]

l = r = n
F = L = R = B = -1
while 1:
    if p:
        while l > r or g() < 0: l -= 1
        b = min(p[l - 1] + g() // l, A)
    else: b, l = A, 0

    f = x * (n - r) + y * b
    if F < f: F, L, R, B = f, l, r, b

    if not p: break
    m += p.pop() - A
    r -= 1
    if m < 0: break

print(F)

p = [(i, B if j < L else q if j < R else A) for j, (q, i) in enumerate(t)]
for i, q in sorted(p): print(q)


f = lambda: list(map(int, input().split()))
g = lambda: m - l * p[l - 1] + s[l]

n, A, x, y, m = f()
t = sorted((q, i) for i, q in enumerate(f()))
p = [q for q, i in t]
s = [0] * (n + 1)
for j in range(n): s[j + 1] = p[j] + s[j]

l = r = n
F = L = R = B = -1
while 1:
    if p:
        while l > r or g() < 0: l -= 1
        b = min(p[l - 1] + g() // l, A)
    else: b, l = A, 0

    f = x * (n - r) + y * b
    if F < f: F, L, R, B = f, l, r, b

    if not p: break
    m += p.pop() - A
    r -= 1
    if m < 0: break

print(F)

p = [(i, B if j < L else q if j < R else A) for j, (q, i) in enumerate(t)]
for i, q in sorted(p): print(q)


f = lambda: list(map(int, input().split()))
g = lambda: m - l * p[l - 1] + s[l]

n, A, x, y, m = f()
t = sorted((q, i) for i, q in enumerate(f()))
p = [q for q, i in t]
s = [0] * (n + 1)
for j in range(n): s[j + 1] = p[j] + s[j]

l = r = n
F = L = R = B = -1
while 1:
    if p:
        while l > r or g() < 0: l -= 1
        b = min(p[l - 1] + g() // l, A)
    else: b, l = A, 0

    f = x * (n - r) + y * b
    if F < f: F, L, R, B = f, l, r, b

    if not p: break
    m += p.pop() - A
    r -= 1
    if m < 0: break

print(F)

p = [(i, B if j < L else q if j < R else A) for j, (q, i) in enumerate(t)]
for i, q in sorted(p): print(q)


f = lambda: list(map(int, input().split()))
g = lambda: m - l * p[l - 1] + s[l]

n, A, x, y, m = f()
t = sorted((q, i) for i, q in enumerate(f()))
p = [q for q, i in t]
s = [0] * (n + 1)
for j in range(n): s[j + 1] = p[j] + s[j]

l = r = n
F = L = R = B = -1
while 1:
    if p:
        while l > r or g() < 0: l -= 1
        b = min(p[l - 1] + g() // l, A)
    else: b, l = A, 0

    f = x * (n - r) + y * b
    if F < f: F, L, R, B = f, l, r, b

    if not p: break
    m += p.pop() - A
    r -= 1
    if m < 0: break

print(F)

p = [(i, B if j < L else q if j < R else A) for j, (q, i) in enumerate(t)]
for i, q in sorted(p): print(q)


f = lambda: list(map(int, input().split()))
g = lambda: m - l * p[l - 1] + s[l]

n, A, x, y, m = f()
t = sorted((q, i) for i, q in enumerate(f()))
p = [q for q, i in t]
s = [0] * (n + 1)
for j in range(n): s[j + 1] = p[j] + s[j]

l = r = n
F = L = R = B = -1
while 1:
    if p:
        while l > r or g() < 0: l -= 1
        b = min(p[l - 1] + g() // l, A)
    else: b, l = A, 0

    f = x * (n - r) + y * b
    if F < f: F, L, R, B = f, l, r, b

    if not p: break
    m += p.pop() - A
    r -= 1
    if m < 0: break

print(F)

p = [(i, B if j < L else q if j < R else A) for j, (q, i) in enumerate(t)]
for i, q in sorted(p): print(q)


f = lambda: list(map(int, input().split()))
g = lambda: m - l * p[l - 1] + s[l]

n, A, x, y, m = f()
t = sorted((q, i) for i, q in enumerate(f()))
p = [q for q, i in t]
s = [0] * (n + 1)
for j in range(n): s[j + 1] = p[j] + s[j]

l = r = n
F = L = R = B = -1
while 1:
    if p:
        while l > r or g() < 0: l -= 1
        b = min(p[l - 1] + g() // l, A)
    else: b, l = A, 0

    f = x * (n - r) + y * b
    if F < f: F, L, R, B = f, l, r, b

    if not p: break
    m += p.pop() - A
    r -= 1
    if m < 0: break

print(F)

p = [(i, B if j < L else q if j < R else A) for j, (q, i) in enumerate(t)]
for i, q in sorted(p): print(q)


f = lambda: list(map(int, input().split()))
g = lambda: m - l * p[l - 1] + s[l]

n, A, x, y, m = f()
t = sorted((q, i) for i, q in enumerate(f()))
p = [q for q, i in t]
s = [0] * (n + 1)
for j in range(n): s[j + 1] = p[j] + s[j]

l = r = n
F = L = R = B = -1
while 1:
    if p:
        while l > r or g() < 0: l -= 1
        b = min(p[l - 1] + g() // l, A)
    else: b, l = A, 0

    f = x * (n - r) + y * b
    if F < f: F, L, R, B = f, l, r, b

    if not p: break
    m += p.pop() - A
    r -= 1
    if m < 0: break

print(F)

p = [(i, B if j < L else q if j < R else A) for j, (q, i) in enumerate(t)]
for i, q in sorted(p): print(q)


def main():
    from bisect import bisect
    n, A, cf, cm, m = list(map(int, input().split()))
    skills = list(map(int, input().split()))
    xlat = sorted(list(range(n)), key=skills.__getitem__)
    sorted_skills = [skills[_] for _ in xlat]
    bottom_lift, a, c = [], 0, 0
    for i, b in enumerate(sorted_skills):
        c += i * (b - a)
        bottom_lift.append(c)
        a = b
    root_lift, a = [0], 0
    for b in reversed(sorted_skills):
        a += A - b
        root_lift.append(a)
    max_level = -1
    for A_width, a in enumerate(root_lift):
        if m < a:
            break
        money_left = m - a
        floor_width = bisect(bottom_lift, money_left)
        if floor_width > n - A_width:
            floor_width = n - A_width
        money_left -= bottom_lift[floor_width - 1]
        if floor_width > 0:
            floor = sorted_skills[floor_width - 1] + money_left // floor_width
            if floor > A:
                floor = A
        else:
            floor = A
        level = cf * A_width + cm * floor
        if max_level < level:
            max_level, save = level, (A_width, floor, floor_width)
    A_width, floor, floor_width = save
    for id in xlat[:floor_width]:
        skills[id] = floor
    for id in xlat[n - A_width:]:
        skills[id] = A
    print(max_level)
    print(' '.join(map(str, skills)))


def __starting_point():
    main()




# Made By Mostafa_Khaled

__starting_point()

n,A,cf,cm,mN = list(map(int,input().split()))

a = list(map(int,input().split()))
aCOPY = []
for elem in a:
    aCOPY.append(elem)
a.sort()

aPartialSum = [0]

for elem in a:
    aPartialSum.append(aPartialSum[-1] + elem)

maxScore = 0
ansMAXIBound = 0
ansMAXI = 0
ansMIN = 0
for MAXI in range(n + 1):
    currentScore = cf * MAXI
    if MAXI >= 1:
        mN -= (A - a[-MAXI])
    if mN < 0:
        break
    if MAXI == n:
        maxScore = currentScore + A * cm
        ansMAXIBound = 0
        ansMAXI = 10 ** 10
        ansMIN = 0
    # Find the maximum of minimum
    l = a[0]
    r = A - 1

    while l < r:
        m = (l + r + 1) // 2
        lA = 0
        rA = n - MAXI - 1
        while lA < rA:
            mA = (lA + rA) // 2
            if a[mA] > m:
                rA = mA - 1
            if a[mA] < m:
                lA = mA + 1
            if a[mA] == m:
                lA = mA
                rA = mA
                break
        lA = min(lA,n - MAXI - 1)
        if a[lA] > m:
            lA -= 1
        expenditure = (lA + 1) * m - aPartialSum[lA + 1]
        if expenditure > mN:
            r = m - 1
        else:
            l = m
    currentScore += l * cm
    if currentScore > maxScore:
        maxScore = currentScore
        ansMAXIBound = a[-MAXI]
        ansMAXI = MAXI
        ansMIN = l

print(maxScore)
inclCount = 0
for i in range(n):
    if aCOPY[i] > ansMAXIBound and inclCount < ansMAXI:
        aCOPY[i] = A
        inclCount += 1
for i in range(n):
    if aCOPY[i] == ansMAXIBound and inclCount < ansMAXI:
        aCOPY[i] = A
        inclCount += 1
    if aCOPY[i] < ansMIN:
        aCOPY[i] = ansMIN
print(" ".join(map(str,aCOPY)))