题目描述

一年一度的暑假又到来啦！又到了 Joyskid 的线下集训营兑换小零食的环节。

强哥的班级总共有 $n$ 个人，他们要兑换 $m$ 种不同的零食。

第 $i$ 个人会兑换 $a_i$ 个每一种零食。

而对于第 $i$ 种零食而言，每个人都需要花 $l_i$ 秒时间来挑选，并且如果同时挑选零食的人需要的零食数量超过了 $v_i$，强哥就会不得不找波哥要求补货，因为不够换。

强哥并不想麻烦波哥，他现在可以随意地安排他班上 $n$ 个人的顺序，并且可以在任意时间让他们开始从第 $1$ 种零食开始兑换（兑换的顺序按照零食编号升序排列），他想知道第一个开始换的人和最后一个开始换的人他们开始换零食的时间差的最小值。

当然，如果实在是必须麻烦波哥，就输出 $-1$。

输入格式

第一行两个数 $n,m$。

第二行有 $n$ 个数，其中第 $i$ 个数是 $a_i$。

然后有 $m$ 行，其中第 $i$ 行两个数分别是 $l_i,v_i$。

输出格式

只有一个数，按照题目描述输出。

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

数据范围

• $2\ \leq\ n\ \leq\ 8$
• $1\ \leq\ m\ \leq\ 10^5$
• $1\ \leq\ a_i,l_i,v_i\ \leq\ 10^8$