传感器优化困境

题目描述

作为 Keyence 的工厂管理者,你想监控传送带上的几个区段。需要监控的区段共有 $N$ 个,第 $i$ 个区段的长度为 $D_i$ 米。

可以选择两种类型的传感器,以下是各传感器的信息:

类型 $j$ 传感器($1 \le j \le 2$):可以监控长度为 $L_j$ 米的区段。 每台价格为 $C_j$,该类型传感器总共最多可以使用 $K_j$ 台。

可以将一个区段分割成多个区段进行监控。 传感器监控的区段有重叠,或者超过想监控的区段长度,都没有关系。 例如,当 $L_1=4$、$L_2=2$ 时,可以用 1 台类型 1 传感器监控长度为 3 米的区段,也可以用 1 台类型 1 和 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 台类型 1 传感器和 4 台类型 2 传感器监控全部区段:

• 用 1 台类型 1 传感器监控第一个区段。
• 用 1 台类型 1 和 1 台类型 2 传感器监控第二个区段。
• 用 1 台类型 1 和 3 台类型 2 传感器监控第三个区段。

此时,所需传感器的总费用为 $3\times 3 + 2\times 4 = 17$,这是最小值。

3
3 5 10
4 3 3
2 2 3

-1

2
4 8
3 1 100
4 10000 100

5

完全不使用某种类型的传感器也没有关系。

数据范围

• $1 \le N \le 100$
• $1 \le D_i, L_j \le 10^5$
• $1 \le C_j \le 10^9$
• $1 \le K_j \le 10^3$
• 所有输入值均为整数