分数: 500 点
问题陈述
作为 Keyence 的工厂经理,您想要监控传送带上的多个部分。总共有 N 要监视的部分以及该部分的长度 i第节是 D_i 米。
有两种类型的传感器可供选择,下面是有关每种传感器的一些信息。
- 类型-j 传感器 (1\leq j \leq 2):可以监控一段长度 L_j 米。 价格是 C_j 每个传感器,您最多可以使用 共有 K_j 种类型的传感器。
您可以将一个区域分成多个区域进行监控。 如果传感器监控的部分重叠,或者它们监控的长度超过了您想要监控的部分的长度,那就没问题。 例如,当 L_1=4 和 L_2=2,您可以使用一种类型 -1 传感器监控一段长度 3 米,或使用一种类型-1 和一种类型-2 传感器监控一段长度 5 米。
判断是否可以监控所有 N 部分,如果可能的话,找到必要传感器的最小总成本。
约束
- 1\leq N \leq 100
- 1\leq D_i,L_j \leq 10^5
- 1\leq C_j \leq 10^9
- 1\leq K_j \leq 10^3
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N D_1 D_2 \dots D_N L_1 C_1 K_1 L_2 C_2 K_2
输出
如果无法监控所有 N 部分,打印 -1。否则,打印必要传感器的最小总成本。
示例输入 1
3 3 5 10 4 3 3 2 2 6
示例输出 1
17
您可以使用三种类型监视所有部分1 传感器和四种类型-2 传感器如下。
- 使用一种类型-1 传感器监控第一部分。
- 使用一种类型-1 和一种类型-2 传感器监控第二部分。
- 使用一种类型-1 和三种类型-2 传感器监控第三节。
在这种情况下,必要传感器的总成本为 3\times 3 + 2\times 4 = 17,这是最小值。
示例输入 2
3 3 5 10 4 3 3 2 2 3
示例输出 2
-1
示例输入 3
2 4 8 3 1 100 4 10000 100
示例输出 3
5
如果根本不使用一种类型的传感器也没关系。