鼠鼠题

题号：NC313720
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 从左到右依次有着 $n$ 个房间，编号为 $1, 2, \dots, n$ 。一开始每个房间 $i$ 中都住着一只体力值为 $a_i$ 的 Jerry。
$\hspace{15pt}$ Tom 可以在房间之间不限次数的左右移动，若当前在房间 $i$ ：
$\hspace{23pt}\bullet\,$ 当 $1 < i \le n$ 时，可以移动到房间 $i - 1$ 。
$\hspace{23pt}\bullet\,$ 当 $1 \le i < n$ 时，可以移动到房间 $i + 1$ 。

$\hspace{15pt}$ 当 Tom 进入一个仍存在 Jerry 的房间 $i$ 时：
$\hspace{23pt}\bullet\,$ 若当前攻击力 $y' \geq a_i$ ，Tom 将抓住该 Jerry，并使攻击力 $y'$ 增加 $a_ i$ ；
$\hspace{23pt}\bullet\,$ 否则 Tom 将立即被击败，无法继续行动。

$\hspace{15pt}$ 现有 $q$ 次独立询问，每次询问给定 Tom 进入的初始房间编号 $x$ 和初始攻击力 $y$ （他第一次进入房间 $x$ 时就会立即发生一次战斗）。请计算在不被击败的前提下，他最多能抓住多少只 Jerry。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入两个正整数  和 ，表示房间数量和询问次数。
第二行输入  个正整数 ，表示每个房间 Jerry 的体力值。
此后  行，第  行输入两个正整数 ，表示第  次询问的起始房间、初始攻击力。

除此之外，保证单个测试文件的  之和、 之和均不超过 。

输出描述:

对于每一次询问，新起一行输出一个整数，表示最多能抓住的 Jerry 数量。

示例1

输入

复制

1
10 5
1 9 1 2 4 6 30 100 1 2
3 1
3 7
8 99
9 1
1 8

输出

复制