[R42D]超市 - 代码源竞赛平台

时空限制

1S/512M

题目描述

apiadu 带着 $q$ 个好朋友去超市买礼物。

超市正在举办特别活动，收银台展示了两个长度为 $n$ 的正整数数组 $a$ 和 $b$。这两个数组都是单调递增的（即对于任意 $i < j$，有 $a_i < a_j$ 且 $b_i < b_j$），并且保证 $a_1=1$。

活动的规则如下： 当 apiadu 支付 $c$ 元（$c$ 为正整数）时，收银员会找到一个最大的下标 $d$，使得 $a_d \le c$。此时，apiadu 获得的礼物价值为 $c + b_d$。

apiadu 需要为 $q$ 个朋友各买一份礼物。第 $i$ 个朋友希望得到的礼物价值至少为 $w_i$。请你帮 apiadu 计算，为了满足每个朋友的要求，他最少需要支付多少元钱？

格式

输入格式

第一行包含两个整数 $n, q$，分别表示数组长度和朋友的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组 $a$。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示数组 $b$。

接下来 $q$ 行，每行一个整数 $w_i$，表示第 $i$ 个朋友期望的礼物价值下限。

输出格式

输出共 $q$ 行，每行一个整数。第 $i$ 行表示满足第 $i$ 个朋友要求所需的最少支付金额。

样例

样例输入 #1

3 2
1 3 5
10 20 30
15
36

样例输出 #1

3
6

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	$n, q \le$	$a_n, b_n, w_i \le$	分数
$1$	$1000$		$30$
$2$	$2 \times 10^5$	$10^9$	$70$

对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5$，$1 = a_1 < a_2 < \dots < a_n \le 10^9$，$0 \le b_1 < b_2 < \dots < b_n \le 10^9$，$1 \le w_i \le 10^9$。