题目描述

要将 $m$ 项探测任务按给定顺序安排到连续 $n$ 个时隙。第 $j$ 个时隙的干扰强度为 $a_j$，第 $i$ 项任务占用连续 $b_i$ 个时隙。记 $l_i$ 为第 $i$ 项任务的起始时隙，则其占用区间为 $[l_i,l_i+b_i-1]$。

安排须满足：

1. 任务占用互不重叠：对任意 $i<j$，有 $l_i+b_i-1<l_j$；任务之间可空出任意个时隙。
2. 任务保持给定顺序：$l_1<l_2<\dots<l_m$。
3. 均落在时隙范围内：$1\le l_i$ 且 $l_i+b_i-1\le n$。

峰值干扰为

求所有合法安排下峰值干扰的最小值。

输入描述

第一行一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行两个正整数 $n,m$，表示时隙数和任务数。

第二行 $n$ 个正整数 $a_1,a_2,\dots,a_n$，表示每个时隙的干扰强度。

第三行 $m$ 个正整数 $b_1,b_2,\dots,b_m$，表示每项任务占用的时隙数。

输出描述

对于每组测试数据，输出一行一个整数，表示峰值干扰的最小值。

样例1

输入

2
7 2
8 1 3 5 2 1 4
2 3
6 3
2 8 1 1 3 1
1 1 2

输出

4
3

说明

第一组：第一项任务放在 $[2,3]$（覆盖 $1,3$，最大值 $3$），第二项放在 $[5,7]$（覆盖 $2,1,4$，最大值 $4$）。峰值干扰为 $\max(3,4)=4$。若要求峰值不超过 $3$，则时隙 $1$、$4$、$7$ 不可用，剩余连续段长度不足以放下长度为 $3$ 的第二项任务。

第二组：三项任务分别放在时隙 $1$、$3$ 与 $[4,5]$（覆盖 $2$；$1$；$1,3$），峰值干扰为 $\max(2,1,3)=3$。若要求峰值不超过 $2$，则时隙 $2$、$5$ 不可用，无法为第三项任务找到长度为 $2$ 的连续段。

数据范围

$1\le T\le 200000$，所有测试数据的 $n$ 之和 $\le 200000$，$1\le n$，$1\le m$，$1\le a_i\le 10^9$，$1\le b_i\le n$，$\sum b_i\le n$。