103255: [Atcoder]ABC325 F - Sensor Optimization Dilemma

Problem Statement

As the factory manager of Keyence, you want to monitor several sections on a conveyor belt. There are a total of $N$ sections you want to monitor, and the length of the $i$-th section is $D_i$ meters.

There are two types of sensors to choose from, and below is some information about each sensor.

• Type-$j$ sensor $(1\leq j \leq 2)$: Can monitor a section of length $L_j$ meters. The price is $C_j$ per sensor, and you can use at most $K_j$ sensors of this type in total.

You can divide one section into several sections for monitoring. It is fine if the sections monitored by the sensors overlap, or if they monitor more than the length of the section you want to monitor. For example, when $L_1=4$ and $L_2=2$, you can use one type-$1$ sensor to monitor a section of length $3$ meters, or use one type-$1$ and one type-$2$ sensor to monitor a section of length $5$ meters.

Determine whether it is possible to monitor all $N$ sections, and if it is possible, find the minimum total cost of the necessary sensors.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$D_1$ $D_2$ $\dots$ $D_N$
$L_1$ $C_1$ $K_1$
$L_2$ $C_2$ $K_2$

Output

If it is impossible to monitor all $N$ sections, print -1. Otherwise, print the minimum total cost of the necessary sensors.

Sample Input 1

3
3 5 10
4 3 3
2 2 6

Sample Output 1

17

You can monitor all sections by using three type-$1$ sensors and four type-$2$ sensors as follows.

• Use one type-$1$ sensor to monitor the first section.
• Use one type-$1$ and one type-$2$ sensor to monitor the second section.
• Use one type-$1$ and three type-$2$ sensors to monitor the third section.

In this case, the total cost of the necessary sensors is $3\times 3 + 2\times 4 = 17$, which is the minimum.

Sample Input 2

3
3 5 10
4 3 3
2 2 3

Sample Output 2

-1

Sample Input 3

2
4 8
3 1 100
4 10000 100

Sample Output 3

5

It is fine if one type of sensor is not used at all.

问题描述

作为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

如果完全不使用一种类型的传感器也是可以的。