该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

输入格式

第一行包含两个整数 $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$ 个朋友要求所需的最少支付金额。

3 2
1 3 5
10 20 30
15
36

3
6

数据规模与约定

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

对于 $100$% 的数据：

• $1 \le n, q \le 2 \times 10^5$
• $1 = a_1 < a_2 < \cdots < a_n \le 10^9$
• $0 \le b_1 < b_2 < \cdots < b_n \le 10^9$
• $1 \le w_i \le 10^9$