Description

贝茜的生日快到了，她希望在接下来的 D 天（1 <= D <= 100,000；70% 的测试数据满足 1 <= D <= 500）里庆祝。奶牛们注意力短暂，所以贝茜想要提供玩具来娱乐它们。她计算出她在第 i 天需要 T_i（1 <= T_i <= 50）个玩具。

贝茜的幼儿园为其有抱负的牛程序员提供许多服务，包括一个玩具店，玩具售价为 Tc（1 <= Tc <= 60）美元。贝茜希望通过重复使用玩具来省钱，但农夫约翰担心传染病，要求玩具在使用前进行消毒。（玩具店在销售玩具时会对其进行消毒。）

农场附近的两个消毒服务提供便捷的全套服务。第一个服务收费 C1 美元，需要 N1 个晚上完成；第二个服务收费 C2 美元，需要 N2 个晚上完成（1 <= N1 <= D；1 <= N2 <= D；1 <= C1 <= 60；1 <= C2 <= 60）。贝茜在派对后将玩具送去消毒，如果是一个晚上的服务，她可以在第二天早上支付并取回玩具，或者如果需要更多晚上的消毒，则在之后的早晨取回。

作为一头有学问的奶牛，贝茜已经学会了节省金钱的价值。帮助她找到为她的派对提供玩具的最便宜的方法。

POINTS: 400

Input Format

• 第 1 行：六个用空格分隔的整数：D, N1, N2, C1, C2, Tc

• 第 2 行到第 D+1 行：第 i+1 行包含一个整数：T_i

Output Format

• 第 1 行：为贝茜的生日派对提供安全卫生玩具的最低成本。

4 1 2 2 1 3 
8 
2 
1 
6 

35 

Hint

贝茜希望庆祝 4 天，第一天需要 8 个玩具，第二天需要 2 个玩具，第三天需要 1 个玩具，第四天需要 6 个玩具。第一个消毒服务需要 1 天，收费 2 美元，第二个需要 2 天，收费 1 美元。购买一个新玩具需要 3 美元。

第 1 天 早上购买 8 个玩具，花费 24 美元；下午开派对。将 2 个玩具送去快速清洗（过夜），其余 6 个玩具送去慢速清洗（两晚）。

第 2 天 从快速清洗处取回 2 个玩具；支付 4 美元。下午开派对。将 1 个玩具送去慢速清洗。

第 3 天 从慢速清洗处取回 6 个玩具并支付 6 美元。下午开派对。

第 4 天 从慢速清洗处取回最后一个玩具（将现场玩具数量恢复到 6 个）；支付 1 美元。开心地开派对，意识到花费了最少的钱。

题面翻译由 ChatGPT-4o 提供。