题目描述

在宇宙的尽头，漂浮着一条神秘的深渊航道，连接着星辰之域与无垠虚空。这条航道曾被远古文明用于星舰航行，但由于时空扭曲，其结构变得异常脆弱。如今，只有精确计算舰队的排列方式，才能确保航行安全，避免陷入无尽的空间乱流。

你的任务是指挥一支由 $N$ 艘星舰组成的舰队，穿越一系列由浮游晶壁组成的航道。每艘星舰都会对航道产生能量干涉，这种干涉可能会影响晶壁的稳定性。如果某一段晶壁在某个时刻所承受的总能量干涉超过其阈值，该晶壁就会立刻破裂，使舰队无法继续前进。

在航行开始前，你可以自由决定舰队的排列顺序，并设置相邻星舰之间的间距。这些间距可以是 $0$ 或任意非负数，但一旦航行开始，舰队的排列方式和间距就不会再改变。

航行规则

1. 舰队编排与航行间距

   • 你需要安排 $N$ 艘星舰的航行顺序，即决定每艘星舰在舰队中的相对位置。
   • 你还可以自由设定相邻两艘星舰之间的航行间距，这些间距可以是任意非负数，但在整个航行过程中，这些间距不会发生变化。
   • 舰队的总航行跨度是从最前方的星舰到最后方星舰之间的最短可能距离，即所有相邻星舰间距的总和。

2. 浮游晶壁的特性

   • 航道由 $M$ 段浮游晶壁组成，每段晶壁具有固定的空间范围 $s_i$，以及其最大可承受能量干涉$c_i$。
   • 在航行过程中，某个时刻一段晶壁内部可能会有多艘星舰完全进入，这时它们的总能量干涉会作用在该晶壁上。
   • 处于晶壁边界上的星舰不算进入晶壁内部，因此它们不会对该晶壁的能量干涉产生影响。
   • 如果某一段晶壁在某一时刻的总能量干涉超过 $c_i$，该晶壁会立刻破碎，导致航行失败。

任务

• 你需要判断是否存在一种舰队编排方式，使得舰队可以成功穿越所有浮游晶壁，即所有晶壁在任何时刻都不会超过其能量干涉阈值。
• 如果可以，请计算首尾星舰之间的最短可能航行跨度，即所有相邻星舰间距的总和，使得舰队仍然可以安全穿越航道。

输入格式

第一行包含两个整数 $N, M$，分别表示星舰的数量和浮游晶壁的数量。

第二行包含 $N$ 个整数 $e_1, e_2, \dots, e_N$，分别表示每艘星舰的能量干涉强度。

接下来的 $M$ 行，每行包含两个整数 $s_i, c_i$，分别表示第 $i$ 段浮游晶壁的空间范围和最大可承受的能量干涉。

输出格式

• 如果舰队无论如何都无法穿越航道，输出 -1。
• 否则，输出最短可能的首尾星舰航行跨度（保证答案是整数）。

数据范围

• $2 \leq N \leq 8$
• $1 \leq M \leq 10^5$
• $1 \leq e_i, s_i, c_i \leq 10^8$

样例

3 2
1 4 2
10 4
2 6

10

2 1
12 345
1 1

-1

8 1
1 1 1 1 1 1 1 1
100000000 1

700000000

8 20
57 806 244 349 608 849 513 857
778 993
939 864
152 984
308 975
46 860
123 956
21 950
850 876
441 899
249 949
387 918
34 965
536 900
875 889
264 886
583 919
88 954
845 869
208 963
511 975

3802

说明

对于样例1：

• 设定舰队排列顺序为 [1, 3, 2]，间距 0, 10。
• 在所有浮游晶壁区域内，最大受干涉总强度均未超过承受极限，任务成功。

对于样例2：

• 无论如何调整舰队顺序或间距，都会导致某个浮游晶壁区域崩塌，任务失败。