← 返回题目列表

AtCoder · abc325_f

I. 传感器优化困境

中文机器翻译题面 查看原题

分数: 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

如果根本不使用一种类型的传感器也没关系。