该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题背景】

兔国边界常年面临着土狼的袭扰。为了防范入侵，兔王在边界设立了 $N$ 个连续的防区。

【问题描述】

兔国在边界设立了 $N$ 个防区，编号为 $1$ 到 $N$。每个防区由于地理位置不同，所需的防御级别也不同，第 $i$ 个防区至少需要 $d_i$ 个防守小队看守才能确保安全。

目前兔王派遣了 $M$ 个防守小队，第 $i$ 个小队负责防守的范围是连续的区间 $[L_i, R_i]$（即可以防守第 $L_i$ 到第 $R_i$ 个防区）。如果一个防区被不少于其需求 $d_i$ 个小队防守，则称该防区是“安全的”。

临近年关，由于军费预算缩减，兔王决定恰好撤销其中 1 个防守小队。为了让防线的漏洞尽可能小，兔王希望在撤销这 1 个小队后，剩下的防区中处于“安全”状态的防区数量尽可能多。

请编程计算，在撤销恰好 1 个小队后，最多能有多少个防区保持安全？

【输入格式】

输入文件为 defense.in。 第一行包含两个正整数 $N$ 和 $M$，分别表示防区的数量和初始防守小队的数量。 第二行包含 $N$ 个整数 $d_1, d_2, \dots, d_N$，依次表示每个防区所需的防守小队数量。 接下来 $M$ 行，每行包含两个正整数 $L_i$ 和 $R_i$，表示第 $i$ 个小队负责的防守区间。

【输出格式】

输出文件为 defense.out。 输出一行一个整数，表示撤销恰好 1 个防守小队后，最多能有多少个防区保持安全。

【输入输出样例 1】

输入 (defense.in)

5 3
2 1 1 2 1
1 3
2 4
4 5

输出 (defense.out)

4

【数据范围与提示】

• 对于 30% 的数据：$1 \le N \le 1000$，$1 \le M \le 1000$。
• 对于 100% 的数据：$1 \le N \le 10^5$，$1 \le M \le 10^5$。每个防区看守需求 $d_i$ 满足 $0 \le d_i \le M$，且队伍区间满足 $1 \le L_i \le R_i \le N$。