CF2248G.No Balance Left

Alisa has a shopping card with an initial balance of $h$. There are $n$ types of products in a supermarket. A product of type $i$ costs $c_i$, and Alisa can buy any number of products of each type.

There are also $m$ rebate activities. The $j$-th activity applies to a purchase if its total cost is at least $a_j$ and gives a rebate of $b_j$.

For each purchase, Alisa performs the following operations:

• She chooses one or more products whose total cost $x$ does not exceed the current balance on her card and pays $x$ using the card.
• Among all rebate activities that apply to this purchase, the one with the largest rebate takes effect and its rebate is added to the card balance. If no rebate activity applies, no rebate is added.

For every $h$ from $1$ to $s$, determine whether Alisa can make the balance on her card equal to $0$ after finitely many purchases.

Alisa 有一张初始余额为 $h$ 的购物卡。超市中有 $n$ 种商品，第 $i$ 种商品的单价为 $c_i$，且 Alisa 可以购买任意数量的每种商品。

此外还有 $m$ 个返现活动。第 $j$ 个返现活动适用于总花费至少为 $a_j$ 的单次购物，并提供金额为 $b_j$ 的返现。

每次购物时，Alisa 执行以下操作：

• 她选择一种或多种商品，使其总花费 $x$ 不超过购物卡当前余额，并用该卡支付 $x$ 元；
• 在所有适用于本次购物的返现活动中，返现金额最大的那个活动生效，其返现金额 $b_j$ 被加到购物卡余额中；若没有适用的返现活动，则不增加任何返现。

对每个从 $1$ 到 $s$ 的 $h$，判断 Alisa 是否能在有限次购物后使购物卡余额恰好变为 $0$。

The first line contains three integers $n$, $m$, and $s$ ($1 \le n, m, s \le 125\,000$) — the number of product types, the number of rebate activities, and the maximum initial balance to consider, respectively.

The second line contains $n$ integers $c_1, c_2, \ldots, c_n$ ($1 \le c_i \le 125\,000$) — the price of a product of each type.

The $i$-th of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le 125\,000$) — the spending threshold and the rebate of the $i$-th activity, respectively.

It is guaranteed that $a_1 \lt a_2 \lt \cdots \lt a_m$ and $b_1 \lt b_2 \lt \cdots \lt b_m$.

第一行包含三个整数 $n$、$m$ 和 $s$（$1 \le n, m, s \le 125\,000$），分别表示商品种类数、返现活动数以及需考虑的最大初始余额。

第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le 125\,000$），表示每种商品的价格。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le 125\,000$），分别表示第 $i$ 个返现活动的消费门槛和返现金额。

保证 $a_1 \lt a_2 \lt \cdots \lt a_m$ 且 $b_1 \lt b_2 \lt \cdots \lt b_m$。

Print $s$ lines. For each $i$ ($1 \le i \le s$), print "YES" if Alisa can make the balance on her card equal to $0$ when its initial balance is $i$, and print "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

输出 $s$ 行。对于每个 $i$（$1 \le i \le s$），若 Alisa 在卡片初始余额为 $i$ 时能够使其余额恰好变为 $0$，则输出 "YES"；否则输出 "NO"。

答案的大小写不限（即大小写均可）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答。

In the first example, Alisa can make the balance equal to $0$ when the initial balance is $15$ as follows:

• She buys one product of each type for a total cost of $4 + 7 = 11$. The balance decreases from $15$ to $4$.
• Since $11 \ge 8$, the rebate of $4$ takes effect. The balance increases from $4$ to $8$.
• She buys one product of the first type for $4$. No rebate activity applies, so the balance decreases from $8$ to $4$.
• She buys one product of the first type again for $4$. No rebate activity applies, so the balance decreases from $4$ to $0$.

Therefore, the $15$-th line of the first example output is "YES".

In the second example, if the initial balance is $4$, Alisa can buy one product of the first type for $4$. Since $4 \lt 6$, no rebate activity applies, and the balance becomes $0$. Therefore, the fourth line of the second example output is "YES". If the initial balance is $1$, no product is affordable, so the first line is "NO".

在第一个例子中，当初始余额为 $15$ 时，阿丽萨可以按如下方式使余额变为 $0$：

• 她购买每种类型的产品各一个，总花费为 $4 + 7 = 11$。余额从 $15$ 减少至 $4$。
• 由于 $11 \ge 8$，返现 $4$ 生效。余额从 $4$ 增加至 $8$。
• 她再次购买一个第一类商品，花费 $4$。此时不满足返现条件，因此余额从 $8$ 减少至 $4$。
• 她再次购买一个第一类商品，花费 $4$。此时仍不满足返现条件，因此余额从 $4$ 减少至 $0$。

因此，第一个例子输出的第 $15$ 行为 "YES"。

在第二个例子中，若初始余额为 $4$，阿丽萨可购买一个第一类商品，花费 $4$。由于 $4 \lt 6$，不触发返现，余额变为 $0$。因此，第二个例子输出的第四行为 "YES"。若初始余额为 $1$，则无法负担任何商品，故第一行为 "NO"。