Lesha 正在玩传奇游戏 hacknet 最近发布的新版本。在这个版本中引入了角色技能机制。现在,每个玩家角色正好有 n 个技能。每个技能都由一个非负整数 ai 表示——当前技能等级。所有技能的最高等级A相同。
除了技能之外,还添加了所有玩家的全球排名。玩家根据所谓的力量进行排名。玩家的力量是以下值的总和:
- 角色已完善的技能数量(即,ai = A),乘以系数cf。
- 所有技能中的最低技能等级(min ai),乘以系数cm。
现在 Lesha 拥有 m 个 hacknetian 货币单位,他愿意花费这些货币。每个货币单位可以将任意技能的当前等级提高 1(如果尚未等于 A)。帮助他花钱,以实现原力的最大可能价值。
输入
输入的第一行包含五个空格分隔的整数 n、A、cf、cm 和 m (1 ≤ n ≤ 100 000、1 ≤ A ≤ 109、0 ≤ cf、cm ≤ 1000、0 ≤ m ≤ 1015)。
第二行正好包含 n 个整数 ai (0 ≤ ai ≤ A),用空格分隔,即当前技能级别。
输出
在第一行打印角色使用不超过 m 货币单位可以达到的力量最大值。
在第二行打印 n 个整数 a'i (ai ≤ a'i ≤ A),即一个人必须达到的技能等级才能达到指定的原力值,同时使用不超过 m 个货币单位。数字应该用空格分隔。
示例
输入 #1
3 5 10 1 5 1 3 1
输出 #1
12 2 5 2
输入 #2
3 5 10 1 339 1 3 1
输出 #2
35 5 5 5
注意
在第一个测试中,最佳策略是将第二个技能增加到最大,并将其他两个技能增加 1。
在第二次测试中,应将所有技能增加到最大。