题目描述

一条走廊上从左到右排列着 $n$ 个站点。第 $i$ 个站点的开启难度为正整数 $h_i$，物资量为正整数 $w_i$。

对于一次需求量为 $K$ 的询问，你需要求出最小的非负整数 $H$，使得可以完成以下选择：

• 选择一个连续区间 $[l,r]$，其中 $1\le l\le r\le n$；
• 可以在区间内抢修至多一个站点 $x$；
• 除被抢修的站点外，区间内每个站点 $i$ 都必须满足 $h_i\le H$；
• 被抢修的站点不受其开启难度限制，并且它的物资量仍计入收集量；
• 区间内所有站点的物资量之和至少为 $K$。

你也可以不抢修任何站点，此时区间内所有站点都必须满足 $h_i\le H$。

每次询问彼此独立，询问不会改变任何站点。

输入格式

从文件 corridor.in 中读取数据。

第一行包含两个正整数 $n,q$，分别表示站点数和询问数。

第二行包含 $n$ 个正整数 $h_1,h_2,\ldots,h_n$。

第三行包含 $n$ 个正整数 $w_1,w_2,\ldots,w_n$。

接下来 $q$ 行，每行包含一个正整数 $K$，表示一次询问的需求量。

输出格式

输出到文件 corridor.out 中。

输出 $q$ 行。对于每次询问，输出一个整数，表示满足要求的最小非负整数 $H$。

样例

5 5
2 5 2 5 2
3 4 5 6 7
7
8
18
19
25

0
2
2
5
5

6 5
4 1 6 2 5 3
2 2 2 2 2 2
2
3
5
7
10

0
1
2
4
5

样例解释

样例 #1 中，当 $H=0$ 时，可以只选择并抢修第 $5$ 个站点，收集 $7$ 单位物资。当 $H=2$ 时，抢修第 $4$ 个站点并选择区间 $[3,5]$，可以收集 $5+6+7=18$ 单位物资；但此时一次选择无法收集至少 $19$ 单位物资。当 $H=5$ 时可以选择整条走廊。

样例 #2 中，当 $H$ 依次为 $0,1,2,3,4,5,6$ 时，一次选择最多能收集的物资量依次为 $2,4,6,6,8,12,12$，由此得到各次询问的答案。

数据规模与约定

对于所有数据，保证：

• $1\le n,q\le 2\times 10^5$；
• 对于所有 $1\le i\le n$，$1\le h_i,w_i\le 10^9$；
• 对于每次询问，$1\le K\le 10^9$ 且 $K\le \sum_{i=1}^{n}w_i$。

本题采用子任务捆绑计分。每个子任务内的所有测试点均通过，才能获得该子任务的分数；各子任务独立计分。

大样例下载