U730052 边缘世界：轨道交易

你的殖民地刚刚度过了一场严酷的“剧毒寒霜”，急需补充物资。幸运的是，一艘闪耀世界的轨道商船刚好进入了通讯控制台的连接范围。 这艘商船使用一种特殊的数字加密芯片进行交易。受限于底层数据结构的特性，这种芯片货币的所有面额都被严格限制为 $2^x$（$x \in \mathbb{N}$，即 $x$ 为非负整数）。 殖民地的仓库里存放着之前探索远古威胁时搜刮来的若干种不同面额的芯片货币。商船上列出了 $n$ 件殖民地所需的物资，每件物品都有明确的标价。 由于商船资金充裕，拥有该系统下所有面额的货币且数量无限，因此**允许找零**。为了确保殖民地能在边缘星系存活下去，你需要计算出最多能够买到多少件物资。

现在有 $n$ 件商品，第 $i$ 件商品的价格为 $p_i$。你拥有 $m$ 种不同面额的货币，每种货币具有指定的面额指数和数量。 在交易时**允许找零**。请问根据你拥有的货币种类和数量，你最多能够购买多少件商品？

第一行包含两个正整数 $n$ 和 $m$，分别表示商品的数量和你拥有的货币种类数。 第二行包含 $n$ 个正整数 $p_1, p_2, \dots, p_n$，表示每件商品的价格。 接下来 $m$ 行，每行包含两个非负整数 $x_i$ 和 $c_i$，表示你拥有 $c_i$ 枚面额为 $2^{x_i}$ 的货币。

输出一行一个整数，表示你最多能够购买的商品总数。

**【样例解释 #1】** 你拥有 $3$ 枚面额为 $2^0=1$ 的货币，以及 $2$ 枚面额为 $2^2=4$ 的货币。你的总资金为 $3 \times 1 + 2 \times 4 = 11$。 商品价格分别为 $3, 7, 4, 10$。你可以选择购买价格为 $3$ 和 $7$ 的商品（共耗资 $10$），或购买价格为 $3$ 和 $4$ 的商品（共耗资 $7$）。无论如何组合，最多只能购买 $2$ 件商品。 **【数据规模与约定】** * 对于 $30\%$ 的数据，保证 $1 \le n, m \le 10^3$，$0 \le x_i \le 30$。 * 对于 $100\%$ 的数据，保证 $1 \le n, m \le 10^5$，$1 \le p_i \le 10^9$，$0 \le x_i \le 60$，$1 \le c_i \le 10^9$。 * 保证输入的 $x_i$ 互不相同，且你初始拥有的货币总价值不超过 $10^{18}$（保证在 64 位有符号整数的表示范围内）。