Sensor Optimization Dilemma

题目描述

作为 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$ 段，如果可以，求出必要传感器的最小总花费。

输入格式

输入从标准输入给出，格式如下： $N$ $D_1$ $D_2$ $\dots$ $D_N$ $L_1$ $C_1$ $K_1$ $L_2$ $C_2$ $K_2$

输出格式

如果无法监控所有 $N$ 段，输出 $-1$。否则，输出必要传感器的最小总花费。

3
3 5 10
4 3 3
2 2 6

17

3
3 5 10
4 3 3
2 2 3

-1

2
4 8
3 1 100
4 10000 100

5

提示

$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$ 所有输入值均为整数。你可以按如下方式使用三个类型-$1$ 传感器和四个类型-$2$ 传感器来监控所有段。

用一个类型-$1$ 传感器监控第一段。 用一个类型-$1$ 和一个类型-$2$ 传感器监控第二段。 用一个类型-$1$ 和三个类型-$2$ 传感器监控第三段。

在这种情况下，必要传感器的总花费是 $3\times 3 + 2\times 4 = 17$，这是最小值。
允许某一类型的传感器一个也不使用。

标签: AtCoder|abc325F

来源

AtCoder|abc325F