D - 街灯の設置 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は、一直線の道路沿いにある N 軒の家すべてを照らすために、街灯を設置する計画を立てています。道路は数直線として表され、家 i は座標 X_i に位置しています。どの 2 軒の家も異なる座標にあります。

街灯は全部で M 種類が販売されています。種類 j の街灯は、数直線上の任意の実数座標に設置でき、設置した位置から距離 R_j 以内（すなわち、設置位置との差の絶対値が R_j 以下）にあるすべての家を照らすことができます。種類 j の街灯を 1 基設置するのに費用 C_j がかかります。

各種類の街灯は何基でも設置でき、異なる種類の街灯を混在させて使うこともできます。各街灯はそれぞれ独立に任意の実数座標を選んで設置でき、同じ座標に複数の街灯を設置することも可能です。

すべての N 軒の家が少なくとも 1 基の街灯によって照らされている状態を実現するために必要な、設置費用の合計の最小値を求めてください。

制約

  • 1 \leq N \leq 3000
  • 1 \leq M \leq 3000
  • 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • X_i \neq X_k (i \neq k)
  • 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M
X_1 X_2 \ldots X_N
R_1 C_1
R_2 C_2
\vdots
R_M C_M
  • 1 行目には、家の数を表す N と街灯の種類数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各家の座標を表す X_1, X_2, \ldots, X_N が、スペース区切りで与えられる。
  • 続く M 行にわたって、各街灯の種類の情報が与えられる。
  • 2 + j 行目 (1 \leq j \leq M) には、種類 j の街灯が照らせる距離を表す R_j と、1 基あたりの設置費用を表す C_j が、スペース区切りで与えられる。

出力

すべての家を照らすために必要な設置費用の合計の最小値を 1 行で出力せよ。なお、答えは 64 ビット符号付き整数の範囲に収まることが保証される。

入力例 1

4 2
0 3 8 10
2 5
5 9

出力例 1

9

入力例 2

5 3
1 2 100 105 106
1 3
3 7
10 20

出力例 2

9

入力例 3

12 5
0 4 7 15 16 23 42 43 44 70 85 100
2 4
5 9
10 16
25 35
50 80

出力例 3

32

入力例 4

30 8
0 1 2 50 55 60 120 121 180 240 241 242 500 510 520 900 1000 1100 5000 5010 5020 100000 100010 100030 1000000 1000050 9999990 10000000 500000000 1000000000
1 2
5 8
15 20
50 55
100 90
500 300
10000 1200
1000000000 100000000

出力例 4

50

入力例 5

1 1
1000000000
1 1000000000

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi is planning to install street lights to illuminate all N houses located along a straight road. The road is represented as a number line, and house i is located at coordinate X_i. No two houses are at the same coordinate.

There are M types of street lights available for purchase. A street light of type j can be installed at any real-number coordinate on the number line, and it illuminates all houses within distance R_j from the installation position (that is, all houses whose absolute difference from the installation position is at most R_j). Installing one street light of type j costs C_j.

Each type of street light can be installed any number of times, and different types of street lights can be used together. Each street light can be independently placed at any real-number coordinate, and multiple street lights can be installed at the same coordinate.

Find the minimum total installation cost required to achieve a state where all N houses are illuminated by at least one street light.

Constraints

  • 1 \leq N \leq 3000
  • 1 \leq M \leq 3000
  • 0 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • X_i \neq X_k (i \neq k)
  • 1 \leq R_j \leq 10^9 (1 \leq j \leq M)
  • 1 \leq C_j \leq 10^9 (1 \leq j \leq M)
  • All inputs are integers

Input

N M
X_1 X_2 \ldots X_N
R_1 C_1
R_2 C_2
\vdots
R_M C_M
  • The first line contains N, the number of houses, and M, the number of types of street lights, separated by a space.
  • The second line contains X_1, X_2, \ldots, X_N, the coordinates of each house, separated by spaces.
  • The following M lines provide information about each type of street light.
  • The (2 + j)-th line (1 \leq j \leq M) contains R_j, the illumination distance of type j street light, and C_j, the installation cost per unit, separated by a space.

Output

Output in one line the minimum total installation cost required to illuminate all houses. It is guaranteed that the answer fits within a 64-bit signed integer.

Sample Input 1

4 2
0 3 8 10
2 5
5 9

Sample Output 1

9

Sample Input 2

5 3
1 2 100 105 106
1 3
3 7
10 20

Sample Output 2

9

Sample Input 3

12 5
0 4 7 15 16 23 42 43 44 70 85 100
2 4
5 9
10 16
25 35
50 80

Sample Output 3

32

Sample Input 4

30 8
0 1 2 50 55 60 120 121 180 240 241 242 500 510 520 900 1000 1100 5000 5010 5020 100000 100010 100030 1000000 1000050 9999990 10000000 500000000 1000000000
1 2
5 8
15 20
50 55
100 90
500 300
10000 1200
1000000000 100000000

Sample Output 4

50

Sample Input 5

1 1
1000000000
1 1000000000

Sample Output 5

1000000000