题目描述

题目译自 PA 2015 Runda 1 Siano

农民 Bajtazar 购买了一块面积为 $n$ 公亩的土地，打算在上面种植草料。割下并晒干的草将用作他农场中牲畜的饲料。

这片土地上将种植 $n$ 种草的混合物，每种草总共占据 $1$ 公亩的土地。已知第 $i$ 种草每天的草茎生长速度为 $a_{i}$ 厘米，不受天气条件和土壤肥沃度的影响。同时已知，割下 $1$ 厘米草并晒干后，在 $1$ 公亩土地上可以得到 $1$ 公斤干草。

Bajtazar 拥有一台割草机，可以将其设置为将草割到任意高度 $b$ ——在这种设置下，任何高于 $b$ 厘米的草茎将被割到正好 $b$ 厘米的高度。

拜托克法律要求每次割草后必须记录从割下的草中获得的干草重量。Bajtazar 面临一个选择：要么购买一台秤，要么编写一个程序，根据割草日期和割草机设置估算每次割草后获得的干草重量。他认为第二种选择更方便且成本更低。

我们假设草将在第 $0$ 天午夜种植，并且每次割草都在午夜进行。同时假设将草割到任意高度 $b$ 所需的时间可以忽略不计。

输入格式

输入数据的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 500000)$，分别表示 Bajtazar 土地的面积（单位：公亩，同时也是种植的草种数量）和割草次数。

第二行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$ $(1 \leq a_{i} \leq 10^{6})$，表示各种草的生长速度。

接下来的 $m$ 行描述 Bajtazar 执行的割草操作：第 $i$ 行包含两个整数 $d_{i}$ 和 $b_{i}$ $(1 \leq d_{i} \leq 10^{12}, 0 \leq b_{i} \leq 10^{12})$，表示在第 $d_{i}$ 天，Bajtazar 将草割到 $b_{i}$ 厘米的高度。你可以假设割草描述按时间顺序排列，即 $d_{1} < d_{2} < \ldots < d_{m}$。

此外，你可以假设 Bajtazar 绝不会让土地上某处的草高度超过 $10^{12}$ 厘米。

输出格式

输出应包含恰好 $m$ 行。第 $i$ 行应为第 $i$ 次割草后获得的干草总重量（单位：公斤）。

4 4
1 2 4 3
1 1
2 2
3 0
4 4

6
6
18
0

下表展示了草种 $1, 2, 3, 4$ 在每次割草前后的草茎高度。