CF589G.Hiring

人力资源部的主管决定招聘新员工。为此，他为求职者设计了一项需要在最多 $m$ 个工作日内完成的测试任务。每位求职者都必须通过这个任务。在任意一个第 $j$ 天，求职者在办公室的时间最多为 $t_j$ 个单位时间。

共有 $n$ 名求职者报名应聘并提交了简历。根据提供的数据，主管为每位求职者定义了两个参数：$d_i$ 和 $r_i$。参数 $d_i$ 是第 $i$ 位求职者每天早晨的准备时间，这个时间每天都相同。参数 $r_i$ 是他们完成整个测试任务所需的总时间。

因此，在第 $j$ 天，求职者在办公室的时间包括 $d_i$ 单位时间的准备以及用于任务的时间。求职者可以选择某天不去办公室，这样的话就不需要花费 $d_i$ 单位时间来做准备。

要完成测试任务，求职者需要正好工作 $r_i$ 单位时间（不包括准备时间）。

请找出每位求职者最早能在第几天完成任务。可以跳过一些天不去，但只要去工作就必须先花费 $d_i$ 单位时间准备。

第一行包含两个整数 $n, m$ $ (1 \leq n, m \leq 2 \cdot 10^5)$，分别表示求职者的数量和完成测试任务的最大工作天数。

第二行包含 $m$ 个整数 $t_1, t_2, \ldots, t_m$ $ (1 \leq t_j \leq 10^6)$，代表每个工作日的时间长度。

接下来的 $n$ 行中，每行包含两个整数 $d_i, r_i$ $ (0 \leq d_i \leq 10^6, 1 \leq r_i \leq 10^6)$，分别代表第 $i$ 位求职者每天进行准备所需的时间和完成任务所需的总工作时间。

输出一个包含 $n$ 个整数的序列 $b_1, b_2, \ldots, b_n$，其中 $b_i$ 表示第 $i$ 位求职者可以最早在哪一天完成测试任务。

如果第 $i$ 位求职者在 $m$ 天内无法完成测试任务，则输出 $b_i = 0$。

题目中的天数按照输入顺序从 1 到 $m$ 编号。

本翻译由 AI 自动生成