F - Sensor Optimization Dilemma Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

キーエンスの工場長であるあなたは、ベルトコンベア上のいくつかの区間をセンサーによって監視したいと考えています。 あなたが監視したい区間は全部で N 個あり、i 個目の区間の長さは D_i メートルです。

センサーには 2 種類の候補があり、それぞれのセンサーに関する情報は以下の通りです。

  • センサー j\ (1\leq j \leq 2) : 長さ L_j メートルの区間を監視できる。 価格は 1 個あたり C_j であり、全体で最大 K_j 個まで使用することができる。

1 つの区間をいくつかの区間に分割して監視することもできます。 また、センサーが監視する区間が重なっていたり、監視したい区間の長さより余分に監視していたりしても問題はありません。 例えば、L_1=4,L_2=2 であるとき、センサー 1 を 1 つ使って長さ 3 メートルの区間を監視したり、センサー 1,2 を 1 つずつ使って長さ 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 を 3 つ、センサー 2 を 4 つ使ってすべての区間を監視できます。

  • センサー 1 を 1 つ使って 1 個目の区間を監視する。
  • センサー 1,2 を 1 つずつ使って 2 個目の区間を監視する。
  • センサー 1 を 1 つ、センサー 2 を 3 つ使って 3 個目の区間を監視する。

このとき、必要なセンサーの価格の総和は 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

1 つも使わない種類のセンサーがあっても構いません。

Score : 500 points

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.