Score : $500$ points

问题描述

作为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$个区域，并在可能的情况下，找出所需传感器的最小总成本。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 01:48:36