D. 共享单车

题目描述

小明需要使用$n$次共享单车，第$i$次在第$a_i$分钟。现在有$m$种骑车卡，每种卡需要花费$c_i$元，从购买开始后的$k_i$分钟（买的时候对应的时间算第一分钟）内可以免费骑车。现在小明需要保证他在需要单车时身上至少有一种骑车卡（不关心剩余时间，可以在需要的时刻立即购买），问小明最少要花多少钱？

输入格式

第一行输入一个整数$n, m$

第二行$n$个整数$a_1, a_2, \cdots, a_n$

接下来$m$行，每行两个整数$c_i, k_i$

输出格式

输出一个数字表示答案

输入样例1

10 2
1 3 5 7 9 11 13 15 17 19
2 2
3 3

输出样例1

15

数据范围

对于30%的数据，$n, m \leq 100$

对于60%的数据，$n, m \leq 500$

对于100%的数据，$n \leq 10^5, m\leq 500, a_1 < a_2 < \cdots < a_n, 1 \leq c_i, k_i \leq 10^9$