题目描述

小明是一位木匠，他在自己拥有的

最开始小明埋了n颗树的种子，此时n棵树的高度都为0，由于小明每天都会给所有的树苗施肥，所以树生长的速度飞快，但因为树种子质量不同，施肥后每棵树每天以固定a[i]的速度生长。

接下来的日子里，小明有m天需要木材，对于第D[i]天小明会把所有高度高于B[i]的树收割到B[i]的高度，小明想知道每次他砍木头的总收割量。

输入格式

第一行给定一个t，代表t组测试数据。（1<=t<=10）

对于每组数据，给定n，m代表有n棵树，m次收割操作。

（1<=n,m<=1e5，∑n,∑m<=5e5）

接下来一行，给定每棵树每天可以增长的高度a[i]。（1<=a[i]<=1e5）

下面m行，每行给定D[i]，B[i]，代表第D[i]天收割高于B[i]的树，D[i]保证单调递增。（1<=D[i]<=1e9,1<=B[i]<=1e9）

（数据保证没有任何时刻树的高度的总和超出long long范围）

输出格式

对于每组测试数据输出m行，每行代表收割得到木材长度的总和。

输入输出样例

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

6
14
1
0