AT_abc325_f.[ABC325F] 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；如果可以，输出所需传感器价格总和的最小值。

限制条件

• $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

如下所示，可以使用 3 个 1 号传感器和 4 个 2 号传感器监控所有区间。

• 用 1 个 1 号传感器监控第 1 个区间。
• 用 1 个 1 号和 1 个 2 号传感器监控第 2 个区间。
• 用 1 个 1 号和 3 个 2 号传感器监控第 3 个区间。
  此时所需传感器价格总和为 $3\times 3 + 2\times 4 = 17$，这是最小值。

样例解释 3

可以有某种类型的传感器一个都不使用。

由 ChatGPT 4.1 翻译