题目描述

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

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

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

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

POINTS: $400$

输入格式

• 第 $1$ 行：六个用空格分隔的整数：$D$, $N_1$, $N_2$, $C_1$, $C_2$, $Tc$

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

输出格式

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

4 1 2 2 1 3 
8 
2 
1 
6 

35 

提示

贝茜希望庆祝 $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 提供。