seuOJ9165 - 猪扫货

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：Div.2, 2025 帆软杯

题目描述

题目背景

超市里有 $n$ 个零食货架，每个货架只售卖一种零食。

其中，第 $i$（$1\le i\le n$）种零食的单价为 $a_i$ 元，每位顾客限购 $b_i$ 件。

有 $m$ 只猪闯入超市扫货。其中，第 $i$（$1\le i\le m$）只猪有 $c_i$ 元。

对于每只闯入超市的猪，计算他最多能购买多少件零食。

假设每种零食的数量都足够多。

输入格式

第一行两个整数 $n,m$（$1\le n,m\le2\times10^5$），分别表示货架的数量和猪的数量。

第二行 $n$ 个整数 $a_i$（$1\le a_i\le10^9$），第 $i$ 个数表示第 $i$ 种零食的单价（单位：元）。

第三行 $n$ 个整数 $b_i$（$1\le b_i\le2\times10^5$），第 $i$ 个数表示第 $i$ 种零食限购的件数。

接下来 $m$ 行中的第 $i$ 行有一个整数 $c_i$（$1\le c_i\le2\times10^5$），表示第 $i$ 只猪身上带了多少元钱。

输出格式

输出 $m$ 行，每行一个整数。第 $i$ 行的数表示第 $i$ 只猪最多能购买多少件零食。

样例

样例

输入

3 4
4 100 2
3 100 2
1
10
114514
16

输出

0
3
105
5

解释

第 $1$ 只猪没带钱，无法购买任何零食，因此答案是 $0$。

第 $2$ 只猪可以购买 $2$ 件 $4$ 元的零食和 $1$ 件 $2$ 元的零食。对他来说，虽然也存在其它购买 $3$ 件零食的方案，但不存在购买超过 $3$ 件零食的方案。因此，答案是 $3$。

第 $3$ 只猪是富哥，嘎嘎扫货，大手一挥，只不过超市的限购规定束缚了他的钞能力。

第 $4$ 只猪很懒，懒得解释。