P0902

[USACO2008 Nov]toy 玩具

[USACO2008 Nov]toy 玩具

Bessie 的生日快到了，她计划用 DD 天来庆祝。由于奶牛们很难长时间集中注意力，Bessie 希望每天提供一定数量的玩具让它们保持开心。她已经计算出第 ii 天需要的玩具数量为 TiT_i。

幼儿园里有一家玩具店，可以随时购买经过消毒的新玩具，每个玩具的价格为 TcT_c 美元。每天的聚会结束后，当天使用过的玩具必须经过消毒才能再次使用。Bessie 可以选择以下两种消毒方式：

  • 第一种方式对每个玩具收取 C1C_1 美元，需要 N1N_1 个晚上的时间；
  • 第二种方式对每个玩具收取 C2C_2 美元，需要 N2N_2 个晚上的时间。

如果一个玩具的消毒需要 11 个晚上，那么它在第二天即可重新使用；如果需要 22 个晚上，那么它在第三天才可重新使用。

请帮助 Bessie 安排购买和消毒玩具的方案，使她能够满足每天的玩具需求，并最小化总费用。

输入格式

第一行包含 66 个用空格分隔的整数 D,N1,N2,C1,C2,TcD,N_1,N_2,C_1,C_2,T_c。

接下来 DD 行，第 ii 行包含一个整数 TiT_i，表示第 ii 天需要的玩具数量。

输出格式

输出一个整数，表示满足所有玩具需求所需的最小总费用。

样例输入

4 1 2 2 1 3
8
2
1
6

样例输出

35

数据范围

  • 1≤D≤1051\le D\le 10^5；
  • 对于 70%70\% 的测试数据，1≤D≤5001\le D\le 500；
  • 1≤Ti≤501\le T_i\le 50；
  • 1≤Tc≤601\le T_c\le 60；
  • 1≤N1≤D1\le N_1\le D，1≤N2≤D1\le N_2\le D；
  • 1≤C1≤601\le C_1\le 60，1≤C2≤601\le C_2\le 60。

来源与许可

本题为 USACO 2008 November 试题「toy 玩具」，题面与测试数据整理自 BZOJ。

样例 1

输入

4 1 2 2 1 3
8
2
1
6

输出

35