B - 農場の区画分け 解説 /

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

配点 : 300 点

問題文

高橋君は広大な農場を経営しています。この農場には N 個の畑が東西に一列に並んでおり、各畑には 1 から N までの番号が西から順に割り振られています。畑 i (1 \leq i \leq N) の収穫量は A_i です。

高橋君は農場の管理を効率化するため、これらの畑を M 個の区画に分けることにしました。各区画は連続する番号の畑で構成されます。具体的には、j 番目の区画 (1 \leq j \leq M) は畑 L_j から畑 R_j までの連続した畑で構成されます（L_j \leq R_j）。すべての畑はちょうど1つの区画に属し、区画同士で畑が重複することはありません。なお、区画は入力中で必ずしも西から順に与えられるとは限りません。

各区画の 生産力 を、その区画に含まれる畑の収穫量の合計として定めます。すなわち、j 番目の区画の生産力は A_{L_j} + A_{L_j+1} + \cdots + A_{R_j} です。

高橋君は、区画ごとの生産力のばらつきを把握したいと考えています。生産力の差が大きすぎると、作業員の配置や資材の分配が難しくなるためです。

与えられた区画分けに対して、M 個の区画の生産力の最大値から最小値を引いた値を求めてください。

制約

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • M 個の区画は畑 1 から畑 N までを重複なく過不足なく分割する
  • 区画は入力中で必ずしも西から順に与えられるとは限らない
  • 入力はすべて整数

入力

N M
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 1 行目には、畑の数 N と区画の数 M がスペース区切りで与えられる。
  • 2 行目には、各畑の収穫量 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
  • 続く M 行にわたって、各区画の構成が与えられる。
  • 2 + j 行目 (1 \leq j \leq M) には、j 番目の区画を構成する畑の番号の範囲 L_j と R_j がスペース区切りで与えられる。この区画は畑 L_j から畑 R_j までで構成される。

出力

M 個の区画の生産力の最大値から最小値を引いた値を 1 行で出力せよ。

入力例 1

5 3
10 20 30 40 50
1 2
3 3
4 5

出力例 1

60

入力例 2

8 4
5 15 10 20 25 5 30 10
1 3
4 4
5 6
7 8

出力例 2

20

入力例 3

12 5
100 200 300 150 250 50 400 100 200 300 150 100
1 2
3 5
6 8
9 10
11 12

出力例 3

450

Score : 300 pts

Problem Statement

Takahashi manages a vast farm. The farm has N fields arranged in a row from east to west, and each field is numbered from 1 to N in order from west to east. The harvest yield of field i (1 \leq i \leq N) is A_i.

To improve the efficiency of farm management, Takahashi has decided to divide these fields into M sections. Each section consists of consecutively numbered fields. Specifically, the j-th section (1 \leq j \leq M) consists of consecutive fields from field L_j to field R_j (L_j \leq R_j). Every field belongs to exactly one section, and no field is shared between sections. Note that the sections are not necessarily given in order from west to east in the input.

The productivity of each section is defined as the sum of the harvest yields of all fields contained in that section. That is, the productivity of the j-th section is A_{L_j} + A_{L_j+1} + \cdots + A_{R_j}.

Takahashi wants to understand the variation in productivity among the sections. This is because if the difference in productivity is too large, it becomes difficult to allocate workers and distribute resources.

For the given partitioning, find the value obtained by subtracting the minimum productivity from the maximum productivity among the M sections.

Constraints

  • 1 \leq M \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • The M sections partition fields 1 through N completely without overlap or omission
  • The sections are not necessarily given in order from west to east in the input
  • All input values are integers

Input

N M
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains the number of fields N and the number of sections M, separated by a space.
  • The second line contains the harvest yields A_1, A_2, \ldots, A_N of each field, separated by spaces.
  • The following M lines describe the composition of each section.
  • The (2 + j)-th line (1 \leq j \leq M) contains the range of field numbers L_j and R_j that make up the j-th section, separated by a space. This section consists of fields from field L_j to field R_j.

Output

Output in one line the value obtained by subtracting the minimum productivity from the maximum productivity among the M sections.

Sample Input 1

5 3
10 20 30 40 50
1 2
3 3
4 5

Sample Output 1

60

Sample Input 2

8 4
5 15 10 20 25 5 30 10
1 3
4 4
5 6
7 8

Sample Output 2

20

Sample Input 3

12 5
100 200 300 150 250 50 400 100 200 300 150 100
1 2
3 5
6 8
9 10
11 12

Sample Output 3

450